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

Question

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

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

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

使用标准位运算符，可能还有 popcnt 或等效的。

如果有区别，我希望找到两个字符串之间的差异。假设我有字符串b并且我在两个位置交换位，例如0101110 -> 1101100 => 3- 我需要改变的位之间的popcnt - 在两者之间的位的情况下，所以 popcnt 是 30101110 -> 110110010110

您是否看到了一些巧妙的方式来使用 bithacks？

Answer 1

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

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

---

编辑：

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

---

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

总结答案，您可以使用特定于平台的函数，例如 GCC's __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;
}