c - C中的位计数类似于位旋转黑客

Question

我需要创建一个例程来计算不涉及循环（仅位操作）并且不使用大常量的字中的位。

int x = 0xFFFFFFFF;
x += (~((x >> 1) & 0x55555555)+1);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0F0F0F0F);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003F);

这是我在一些小技巧上发现的，但我可以使用的最大常数是 0xFF ... 不知道该怎么做。

谢谢各位。

Answer 1

例如，您可以使用一个常量数组COUNTS[16]，它是从 0 到 15 的数字的二进制表示中设置的位数。然后：

static inline int byte_count (int x) {
  static const int COUNTS[16] = { 0, 1, 1, 2, 1, /* fill in the rest manually */ };
  return COUNTS[x & 15] + COUNTS[x >> 4];
}

int count(int x) {
  return byte_count(x >> 24) + byte_count((x >> 16) & 255) + byte_count((x >> 8) & 255) + byte_count(x & 255);
}

没有循环，也没有大于 255 的常数。

Answer 2

使用您的算法：

int x = 0xFF;
x |= (x << 8);  // x = 0xFFFF
x |= (x << 16); // x = 0xFFFFFFFF

然后是其余的代码 - 只要它有效。

递归解决方案：

int foo ( int x )
{
    if ( x == 0 )
        return 0;
    return (x & 1) + foo ( x/2 );
}

Answer 3

你的问题已经在这里回答了

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