6

在前一段时间的一次工作面试中，我被要求计算位向量结构（如无符号整数或长整数）中正数（即设置为“1”）的位数。我的解决方案在 C# 中相当简单：

int CountBits(uint input)
{
   int reply = 0;
   uint dirac = 1; 
   while(input != 0)
   {
      if ((input & dirac) > 0) reply++;
      input &= ~dirac;
      dirac<<=1;
   }
   return reply;
}

然后我被要求在不使用不使用任何移位的情况下解决任务：既不是显式的（如“<<”或“>>”）也不是隐式的（如乘以 2）。使用 2 的潜在行（如 0、1、2、4、8、16 等）的“蛮力”解决方案也不行。

有人知道这样的算法吗？

据我了解，它应该是一种或多或少的通用算法，它不依赖于输入位向量的大小。允许所有其他按位运算和任何数学函数。

4

3 回答 3

13

有一个x & (x-1)hack，如果你想一想，它会在最后1一个整数中清除。休息是微不足道的。

于 2011-11-20T10:48:13.770 回答
1

一些处理器具有人口计数指令。如果没有，我相信这是最快的方法（对于 32 位）：

int NumberOfSetBits(int i) {
  i = i - ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

有关完整说明，请参阅此链接：http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

至于不轮班，我认为使用查找表是最好的答案：

int NumberOfSetBits(int i) {
  unsigned char * p = (unsigned char *) &i;
  return BitsSetTable256[p[0]] + BitsSetTable256[p[1]] + 
     BitsSetTable256[p[2]] + BitsSetTable256[p[3]];
}

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++) {
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
于 2011-11-20T10:51:18.667 回答
1

与安东尼布莱克描述的方式相同，但我想更具可读性。

uint32_t bitsum(uint32_t x)
{
    // leafs (0101 vs 1010)
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

    // 2nd level (0011 vs 1100)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

    // 3rd level (nybbles)
    //x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x07070707) + ((x >> 4) & 0x07070707);

    /*
    // 4th level (bytes)
    //x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x000f000f) + ((x >> 8) & 0x000f000f);

    // 5th level (16bit words)
    //return (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return (x & 0x0000001f) + ((x >> 16) & 0x0000001f);
    */
    // since current mask of bits 0x0f0f0f0f
    // result of summing 0f + 0f = 1f
    // x * 0x01010101 will produce
    // sum of all current and lower octets in
    // each octet
    return (x * 0x01010101) >> 24;
}
于 2011-11-20T15:25:05.883 回答