计算64位(长整数)整数的位数？

Question

我已经阅读了这个关于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;
}

这会向val右移一位,count如果最右边的位置位则递增.这是一种可用于任何长度整数的通用算法.