0

识别 64 位掩码中所有设置位位置的最佳方法是什么。假设我的位掩码是 0xDeadBeefDeadBeef，那么最好的方法是识别其中设置位的所有位位置。

long long bit_mask = 0xdeadbeefdeadbeef;
unsigned int bit_pos=0;
while(mask) {
  if((mask&1)==1) {
     printf("Set bit position is:%d \n",bit_pos};
  }
  bit_pos++;
  mask>>=1; 
}

一种方法是循环遍历它，并检查是否设置了一个位，如果设置了，则返回计数位置并继续循环直到 MSB，因此对于 64 位，我将迭代直到遍历所有设置位还是遍历所有 64 位，如果设置了 MSB，但必须有更好的方法吗？

4

5 回答 5

2

Hacker's Delight 中的算法（书）：

int count_bits(long long s)
{
    s = (s&0x5555555555555555L) + ((s>>1)&0x5555555555555555L);
    s = (s&0x3333333333333333L) + ((s>>2)&0x3333333333333333L);
    s = (s&0x0F0F0F0F0F0F0F0FL) + ((s>>4)&0x0F0F0F0F0F0F0F0FL);
    s = (s&0x00FF00FF00FF00FFL) + ((s>>8)&0x00FF00FF00FF00FFL);
    s = (s&0x0000FFFF0000FFFFL) + ((s>>16)&0x0000FFFF0000FFFFL);
    s = (s&0x00000000FFFFFFFFL) + ((s>>32)&0x00000000FFFFFFFFL);

    return (int)s;
}
于 2013-10-14T17:40:08.340 回答
1

除了已经解释的漂亮的小技巧之外，还有其他选择。

这假设您拥有 x86(64)、SSE4、gcc 并使用 -msse4 开关进行编译，您可以使用：

int CountOnesSSE4(unsigned int x)
{
    return __builtin_popcount(x);
}

这将编译成单个 popcnt 指令。如果您需要快速代码，您实际上可以在运行时检查 SSE 并使用可用的最佳功能。

如果您希望 number 有少量的，这也可能很快（并且总是比通常的移位和比较循环快）：

int CountOnes(unsigned int x)
{
    int cnt = 0;
    while (x) {
        x >>= ffs(x);
        cnt++;
    }
    return cnt;
}

在 x86（即使没有 SSE）上，ffs 将编译为单指令（bsf），循环数将取决于循环数。

于 2013-10-15T06:56:44.850 回答
0

如果您正在计算那些，您可以使用快速的黑客喜悦解决方案，但查找表可以（并不总是）更快。而且更容易理解。您可以预先准备一个表，例如 256 个深度项目，表示字节值 0x00 到 0xFF 的计数

0, //0x00
1, //0x01
1, //0x02
2, //0x03
1, //0x04
2, //0x05
2, //0x06
3, //0x07
...

构建该表的代码可能会通过每一个位方法使用缓慢的步骤。

一旦建成，尽管您可以将较大的数字分解为字节

count  = table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
...

如果你有更多的内存，你可以通过表示更宽的数字来使表格更大，一个 65536 深的表格，用于数字 0x0000 到 0xFFFF。

count  = table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;

表格是一种以消耗内存为代价来加快处理速度的通用方法。您能够消耗的内存越多，您可以预先计算（在编译时或之前）而不是实时计算的越多。

于 2013-10-15T12:56:51.643 回答
0

你可以这样做：

long long bit_mask = 0xdeadbeefdeadbeef;

int i;
for (i = 0; i < (sizeof(long long) * 8); i++) {
    int res = bit_mask & 1;
    printf ("Pos %i is %i\n", i, res);
    bit_mask >>= 1;

}
于 2013-10-14T17:11:52.953 回答
0

这取决于您是希望代码清晰还是快速获得结果。我几乎总是在代码中选择清晰性，除非分析另有说明。为清楚起见，您可能会执行以下操作：

int count_bits(long long value) {
    int n = 0;
    while(value) {
        n += (value & 1);
        value >>= 1;
   }
   return n;
}

为了提高性能，您可能想从 X J 的答案中调用 count_bits。

int count_bits(long long s)
{
    s = (s&0x5555555555555555L) + ((s>>1)&0x5555555555555555L);
    s = (s&0x3333333333333333L) + ((s>>2)&0x3333333333333333L);
    s = (s&0x0F0F0F0F0F0F0F0FL) + ((s>>4)&0x0F0F0F0F0F0F0F0FL);
    s = (s&0x00FF00FF00FF00FFL) + ((s>>8)&0x00FF00FF00FF00FFL);
    s = (s&0x0000FFFF0000FFFFL) + ((s>>16)&0x0000FFFF0000FFFFL);
    s = (s&0x00000000FFFFFFFFL) + ((s>>32)&0x00000000FFFFFFFFL);

    return (int)s;
}

这取决于您是否想查看您的代码并对自己说：“是的，这是有道理的”或“我会接受那个人的话”。

我之前在堆栈溢出中被调用过。有些人不同意。一些非常聪明的人选择复杂而不是简单。我相信干净的代码是简单的代码。

如果性能需要，请使用复杂性。如果没有，不要。

另外，考虑代码审查。当有人说“count_bits 是如何工作的？”时，你会说什么？

于 2013-10-14T18:07:21.880 回答