bit-manipulation - 找到主导位

Question

我正在尝试确定一个位串(例如 64 位长)是否至少有 50% 为 1。我四处搜寻并查看了伟大的http://graphics.stanford.edu/~seander/bithacks.html ，但我还没有找到专门针对这个问题的任何内容。

我可以将字符串分成8位 block ，预先计算每个 block 中1的数量，然后通过8次查找和7次加法找到结果。

按字节方法的示例:

10001000 10000010 00111001 00001111 01011010 11001100 00001111 11110111
2      + 2      + 4      + 4      + 4      + 4      + 4      + 7        = 31
    hence 0 dominates.

我只是觉得一定有更好的方法，因为我只是想找到统治者。也许我只是用了错误的名字？

Answer 1

您可以使用分而治之的解决方案 here ，很容易适配32位。或者可能只是一个 popcnt 指令，具体取决于您的硬件。然后你只需检查该值是否小于 32，如果是，则 0 占主导地位，否则 1 占主导地位。

链接中的代码适用于 64 位并插入了支配逻辑: (我在末尾额外右移了 5 位，以检查同一移位中设置的位是否大于 31)

int AtLeastHalfOnes(long long i) {
  i = i - ((i >> 1) & 0x5555555555555555LL);
  i = (i & 0x3333333333333333LL) + ((i >> 2) & 0x3333333333333333LL);
  return (((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0FLL) * 0x0101010101010101LL) >> 61;
}