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

我已经阅读了这个关于32位的SO问题 ，但64位数字呢？ 我应该只屏蔽上下4个字节，对32位执行计数，然后将它们一起添加？

Answer 1

您可以在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位版本如何计算32位整数中的设置位数？

使用约书亚的建议我会把它变成这样：

 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为ulong添加了更安全的版本

Answer 2

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

 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 ，否则不是每一位都被设置，因此通常你需要的迭代次数要少得多。

Answer 3

C＃中的标准答案：

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

这将右移一位，如果设置了最右位，则递增count 。 这是一种可用于任何长度整数的通用算法。