以二进制表示计数1的数量

Question

如果你有足够的内存可以用来计算O(1)中数字的二进制表示中1的数量的有效方法.这是我在网上论坛上发现的一个面试问题,但没有答案.有人可以提出一些建议,我想不出在O(1)时间内做到这一点的方法吗？

Answer 1

这就是汉明重量问题,即人口数量.该链接提到了有效的实现.引用:

通过无限的内存,我们可以简单地创建一个每64位整数的汉明权重的大型查找表

Answer 2

我有一个解决方案,计算O(Number of 1's)时间位:

bitcount(n):
    count = 0
    while n > 0:
        count = count + 1
        n = n & (n-1)
    return count

在最坏的情况下(当数字是2 ^ n - 1时,所有1都是二进制的)它将检查每一位.

编辑:刚刚为bitcount找到了一个非常好的恒定时间,常量内存算法.在这里,用C语言写成:

int BitCount(unsigned int u)
{
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

你可以在这里找到它的正确性证明.

Answer 3

请注意以下事实:n&(n-1)总是消除最不重要的1.

因此我们可以编写用于计算1的数量的代码,如下所示:

count=0;
while(n!=0){
  n = n&(n-1);
  count++;
}
cout<<"Number of 1's in n is: "<<count;

程序的复杂性将是:n的1的数量(总是<32).

Answer 4

我从另一个网站看到了以下解决方案:

int count_one(int x){
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

Answer 5

public static void main(String[] args) {

    int a = 3;
    int orig = a;
    int count = 0;
    while(a>0)
    {
        a = a >> 1 << 1;
        if(orig-a==1)
            count++;
        orig = a >> 1;
        a = orig;
    }

    System.out.println("Number of 1s are: "+count);
}

Answer 6

下面是两个简单的示例（C++ 语言），您可以通过它们来执行此操作。

1. 我们可以使用 简单地计算设置位 (1) __builtin_popcount()。

int numOfOnes(int x) {
  return __builtin_popcount(x);
}

2. 循环遍历整数中的所有位，检查是否设置了某个位，如果设置了则递增计数变量。

int hammingDistance(int x) {
  int count = 0;
  for(int i = 0; i < 32; i++)
    if(x & (1 << i))
      count++;
  return count;
}

Answer 7

   countBits(x){
     y=0;
     while(x){   
       y += x &  1 ;
       x  = x >> 1 ;
     }
   }

而已？