c - 两个位置之间的人口计数

Question

我正在寻找一种在两个位置之间的位串中查找弹出计数的解决方案 例如:

popcnt( 10(0101), 0, 3) = 1
popcnt( 100101(), 0, 0) = 0
popcnt( 10010(1), 0, 1) = 0

** 我假设开放范围并假设从右到左的顺序

使用标准位运算符和可能的 popcnt 或等价物。

如果它有所不同，我正在寻找两个字符串差异之间的 popcnt。假设我有字符串 b 并且我在两个位置交换位，例如 0101110 -> 1101100 => 3 - 我需要 popcnt 在更改的位 - 在 0101110 -> 1101100 的情况下，两者之间的位为 10110，因此 popcnt 为 3

您是否看到一些巧妙的方法可以使用 bithacks 做到这一点？

Answer 1

首先屏蔽值以仅获取相关位:

relevant = (value >> startBit) & ((1 << numOfBits) - 1);

---

编辑:

当 numOfBits == 32(或者更准确地说，当 numOfBits == CHAR_BIT * sizeof(int))时，上面的代码将调用未定义的行为。要解决此问题，您需要对这种情况进行特殊处理(设置 relevant = value)。

---

然后使用此问题中提出的方法之一找到这些位的总体计数:Best algorithm to count the number of set bits in a 32-bit integer .

总结一下答案，您可以使用特定于平台的函数，例如 GCC 的 __builtin_popcount，或者如果您需要一个可移植的解决方案，您可以使用并行前缀算法，例如 Matt Howells 的算法回答:

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