人口数量在两个职位之间

Question

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

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

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

使用标准位运算符以及可能的popcnt或等效运算符.

如果它有所不同,我希望找到两个字符串的差异之间的popcnt.让我说我有字符串b,我在两个位置交换位,例如0101110 -> 1101100 => 3- 我需要改变位之间的popcnt - 在两者之间的位的情况下,所以popcnt是30101110 -> 110110010110

你有没有看到一些巧妙的方法来做bithacks？

Answer 1

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

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

编辑:

以上将在numOfBits == 32(或更准确地说,何时numOfBits == CHAR_BIT * sizeof(int))调用未定义的行为.要解决此问题,您需要对该案例(集relevant = value)进行特殊处理.

然后使用此问题中提出的方法之一找到这些位的填充计数:计算32位整数中设置位数的最佳算法.

总结答案,您可以使用特定于平台的功能,例如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;
}