计算64位（长，大）整数中的位数？

问题描述：

我已阅读了大约32位的this SO question，但64位数呢？我应该屏蔽上下4个字节，在32位上执行计数，然后将它们加在一起？计算64位（长，大）整数中的位数？

答

您可以在这里找到http://en.wikipedia.org/wiki/Hamming_weight

64位版本。它是这样的

static long NumberOfSetBits(long i) 
{ 
    i = i - ((i >> 1) & 0x5555555555555555); 
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333); 
    return (((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56; 
}

这是一个64位版本在这里How to count the number of set bits in a 32-bit integer?

代码形式的使用约书亚的我建议将改变它变成这样：

static int NumberOfSetBits(ulong i) 
{ 
    i = i - ((i >> 1) & 0x5555555555555555UL); 
    i = (i & 0x3333333333333333UL) + ((i >> 2) & 0x3333333333333333UL); 
    return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56); 
}

编辑：我在测试32位版本时发现了一个错误。我添加了缺少的括号。总和应该按位&之前进行，在最后一行

EDIT2增加更安全的版本乌龙

应该是无符号长，以避免被烫伤 – Joshua 2010-04-25 19:40:09

的操作应该是选中。否则，最后一行中的乘法很容易溢出。但是，如果他们没有被检查，我认为它也适用于签署很长时间。即使移位是算术移位，大部分有效位都会按位进行丢弃，第一行中的减法可能会无声地溢出到正确的结果。 – 2010-04-25 20:18:46

答

快速（比使用非标准编译器扩展更便携）的方式：

int bitcout(long long n) 
{ 
    int ret=0; 
    while (n!=0) 
    { 
     n&=(n-1); 
     ret++; 
    } 
    return ret; 
}

你做一个n&=(n-1)每次消除n最后一组位。因此这需要O（设置比特数）时间。

如果你测试每一个比特，你会需要比O（log n）更快的速度 - 除非数字是0xFFFFFFFFFFFFFFFF，否则不是每个比特都被设置），因此通常你需要的迭代次数要少得多。

答

标准答案在C＃：

ulong val = //whatever 
byte count = 0; 

while (val != 0) { 
    if ((val & 0x1) == 0x1) count++; 
    val >>= 1; 
}

这种转移val右移一位，和增量count如果最右边位。这是一个可以用于任何长度整数的通用算法。

计算64位（长，大）整数中的位数？

相关推荐