当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

为啥要用位运算代替取模呢

发表于: 2012-11-14   作者:chenchao051   来源:转载   浏览:
摘要:     在hash中查找key的时候,经常会发现用&取代%,先看两段代码吧,     JDK6中的HashMap中的indexFor方法: /** * Returns index for hash code h. */ static int indexFor(int h, int length) {

 

  在hash中查找key的时候,经常会发现用&取代%,先看两段代码吧,

 

  JDK6中的HashMap中的indexFor方法:

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

Redis2.4中的代码段:

    n.size = realsize;
    n.sizemask = realsize-1;
    //此处略去xxx行
   while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }

 

大家可以看到a%b取模的形式都被替换成了a&(b-1) ,当hashtable的长度是2的幂的情况下(疏忽,一开始没写),两者是等价的,那为什么要用后者呢?

另一方面,为什么hashtable的长度最好要是2的n次方呢,这个不在本次讨论范围之列,原因简单说一下就是1、分布更均匀 2、碰撞几率更小  详情自己思考,JDK中的HashMap就会在初始化时,保证这一点:

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

 

redis中也有类似的保证:

 

/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}

 

 

言归正传,大家都知道位运算的效率最高,这也是&取代%的原因,来看个程序:

int main(int argc, char* argv[])
{
    int a = 0x111;
    int b = 0x222;
    int c = 0;
    int d = 0;

    c = a & (b-1);
    d = a % b;

    return 0;
}

 

 

看反汇编的结果:

13:       c = a & (b-1);
00401044   mov         eax,dword ptr [ebp-8]
00401047   sub         eax,1
0040104A   mov         ecx,dword ptr [ebp-4]
0040104D   and         ecx,eax
0040104F   mov         dword ptr [ebp-0Ch],ecx
14:       d = a % b;
00401052   mov         eax,dword ptr [ebp-4]
00401055   cdq
00401056   idiv        eax,dword ptr [ebp-8]
00401059   mov         dword ptr [ebp-10h],edx

 

可以看到,&操作用了:3mov+1and+1sub  %操作用了:2mov+1cdp+1idiv

 

我们可以查阅Coding_ASM_-_Intel_Instruction_Set_Codes_and_Cycles资料,发现前者只需5个CPU周期,而后者至少需要26个CPU周期(注意,是最少!!!) 效率显而易见。所以以后自己在写的时候,也可以使用前者的写法。

 

 

为啥要用位运算代替取模呢

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
学习Python看到数值运算这部分,看到取模运算,原来不仅正数负数都可以取模,浮点数,甚至复数都可
首先,我们必须明确,为什么要使用J2EE?J2EE优点是什么?使用J2EE的主要原因是多层结构,传统的两
首先,我们必须明确,为什么要使用J2EE?J2EE优点是什么?使用J2EE的主要原因是多层结构,传统的两
位运算 位运算   位运算时把数字用二进制表示之后,对每一位上0或者1的运算。   理解位运算的第
题目: int func(unsigned int i) { Unsigned int temp=i Temp=(temp & 0x55555555)+((temp & 0xaaa
一、六种位运算符: & 按位与 | 按位或 ^ 按位异或 ~ 取反 << 左移 >> 右移 将int型变
这两种运算总是感觉有点迷糊,现在 拨开乌云见天日。 对于整型数a,b来说,取模运算或者求余运算的
快速幂取模 (2012-01-02 21:37:56) 转载▼ 快速幂取模 快速幂取模就是在O(logn)内求出a^n mod b的值
快速幂取模就是在O(logn)内求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c 因此
组合数取模 转 http://hi.baidu.com/scuxy06/blog/item/4b5b3f1921b29b72dab4bddb.html Description
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号