在二进制表示中计算1的数量

Question

如果您有足够的内存来处理，高效计算一个数字的二进制表示中1的数量的方法是O(1)。这是我在一个在线论坛上找到的面试问题，但没有答案。有人能提供一些建议吗？我无法想出如何在O(1)时间内完成。

- TimeToCodeTheRoad

---

所以这个问题想要让你作弊 - “足够”的内存很容易比可观测宇宙中的原子数量还要多。 - harold

这不就是一个长度为MAX_INT的数组吗？ - Boris Treukhov

如果我们有一个数组[0..MAX_INT-1]，其中索引是输入的实际数字，数据是该数字中1的数量（假设它是通过内容可寻址存储器http://en.wikipedia.org/wiki/Content-addressable_memory实现的），那么它不就是O(1)吗？ - Boris Treukhov

这可能是模型面试解决方案，尽管我认为它不会满足纯粹主义者，因为它受机器可寻址内存的数据宽度（例如64位）的限制。对于大于2^64的数字，它将无法工作，而且问题并没有强制执行此限制。如果问题修订为“64位数字”，那么是的，这是一个好的解决方案。 - Tim Gee

另一方面，对于64位数字，旧的位计数方法也是O(1)，几乎不使用内存。 - Daniel Fischer

Answer 1

那就是汉明重量问题，也称为人口统计问题。链接提到了高效实现。引用内容如下：

“如果有无限的内存，我们可以简单地创建一个大的查找表，其中包含每个64位整数的汉明重量。”

- Óscar López

---

对于这个问题的恰当命名我给一个赞。虽然我认为一个完整的回答应该说明，即使使用查找表，查询任何条目的时间也取决于条目的大小，因此不会是O（1）时间。 - Tim Gee

@TimGee LUT访问始终被认为是O(1)的。当您拥有无限的内存时，也拥有无限的地址总线。因此，无论访问哪个地址（= 输入），它始终只需要一个内存访问;-) - Scolytus

@Scolytus，有关“当您拥有无限制的内存时，您也拥有无限制的地址总线”的参考资料吗？ - sasha.sochka

@sasha.sochka 无限内存是一个理论构想。它根本没有地址总线，只是假设您始终拥有足够的内存，并且可以始终以相同的方式访问它，而与其大小无关。因此，在实现无限内存的真实世界中，您的地址总线将始终大于log2（可寻址内存单元数）。 - Scolytus

有一个O(1)算法用于计算二进制位数，它很容易找到并且很可能比任何涉及查找表的解决方案更快。 - Jack Aidley

@JackAidley 链接在哪里？ - Óscar López

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时），它将检查每个比特位。

编辑：刚找到一个非常好的恒定时间、恒定内存的位计数算法。以下是用C语言编写的代码：

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

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

你可以在这里找到其正确性的证明。

- Sufian Latif

---

第二个算法仅在输入大小恒定的情况下具有恒定时间复杂度，对于第一个算法也是如此。由于按位与和减法需要一些时间，因此第一个算法在一般情况下实际上是O(log n)的。 - harold

你的第一个答案是O(log n)，而不是O(1)。你的第二个答案是O(1)，但假设域为32位（输入参数为“unsigned int”）。 - Stephen Quan

实际上，我们应该指定n是什么。对于问题1：如果n是原始数字中的位数，则为O（n * 1的数量），即O（n ^ 2）。如果n是数字的值，则为O（lg ^ 2 n）。 - John Kurlak

还是有人知道另一个带有证明的页面吗？ - mostruash

如果你们中有人想知道 n = n & (n-1) 是什么意思，它会清除 n 的最低有效位（1）。因此，当 n=0 时，我们已经在 while 循环内循环了“answer”次。 - Ε Г И І И О

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）。

- Sriram Mahavadi

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;
    }

- user2555279

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);
}

- akus

---

+1 很好的回答。尝试添加一些解释，特别是对于双向的位移部分，这可能会让一些人感到困惑。 - brimborium

说明：A）如果最低有效位为1，则将计数器增加1（这里是如何工作的：向右移位，然后撤消移位将最低有效位设置为0...如果旧数字和新数字之间的差为1，则已删除1）。B）通过向右移位1来除以2并取整。C）重复直到数字为0。最好只需使用AND运算符即可确定最低有效数字是否为1。 - John Kurlak

你好，我只是好奇，以下代码是否更加高效？if (orig & 1) count++; orig >>= 1; - Chang Hyun Park

甚至更好：count += orig & 1; orig >>= 1; - Noah

Answer 6

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

就这样了吗？

- user40521

Answer 7

以下是两个简单的例子 (使用 C++)，其中之一可以实现这个目标。

1. 我们可以使用 __builtin_popcount() 来简单地计算设置位（1）的数量。

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;
}

- Gaurav Sharma

Answer 8

这将是我在SO生涯中最短的回答：查找表。 显然，“如果你有足够的内存可以使用”意味着我们拥有所有需要的内存（不考虑技术可能性）。现在，您不需要为查找表存储超过一个或两个字节。虽然从技术上讲它将是Ω(log(n))而不是O(1)，但是只读取所需的数字就是Ω(log(n))，因此如果这是问题，则答案是不可能 - 这甚至更短。

他们在面试中期望你给出哪种答案，谁也不知道。

还有一个诀窍：虽然工程师可以接受一个数字并谈论Ω(log(n))，其中n是数字，但计算机科学家会说实际上我们要将运行时间作为输入长度的函数来衡量，因此工程师所谓的Ω(log(n))实际上是Ω(k)，其中k是字节数。尽管如此，正如我之前所说，仅读取一个数字就是Ω(k)，因此我们无法做得比这更好。

- alf

---

当我们处理64位数字时会发生什么？ - leppie

如果你有足够的内存来玩耍，那么首先可以这样做。现在，你不需要为查找表存储超过一个或两个字节（是的，我知道它在技术上将是O(log(n))而不是O(1)，但是为了读取一个数字，你需要O(log(n))）。 - alf

我认为你可以通过硬件并行性以O(1)的速度读取数字，但当你需要对该数字做出决策时（无论是查找表还是部分和操作），你仍然会受到O(log(k))的限制。 - Tim Gee

Answer 9

以下是使用位运算符的C语言解决方案：

    int numberOfOneBitsInInteger(int input) {
      int numOneBits = 0;

      int currNum = input;
      while (currNum != 0) {
        if ((currNum & 1) == 1) {
          numOneBits++;
        }
        currNum = currNum >> 1;
      }
      return numOneBits;
    }

以下是使用2的幂次方的Java解决方案：

    public static int numOnesInBinary(int n) {
    
      if (n < 0) return -1;
    
      int j = 0;
      while ( n > Math.pow(2, j)) j++;
    
      int result = 0;
      for (int i=j; i >=0; i--){
        if (n >= Math.pow(2, i)) {
            n = (int) (n - Math.pow(2,i));
            result++;    
        }
      }
    
      return result;
    }

- eb80

Answer 10

以下方法同样适用。

nofone(int x) {
  a=0;
  while(x!=0) {
    x>>=1;
    if(x & 1)
      a++;
  }
  return a;
} 

- Vigneswaran

---

实际上，这段代码中有一个微不足道的错误。要看到这一点，只需想象当x = 1时会发生什么。 - Andreas Rejbrand