C中的Bit Twiddling-计数位

Question

我想计算在一个非常大的位向量（即100000位）中设置的位。

我目前正在做的是使用指向char的指针（即char*cPtr）来指向位数组的开头。然后：

1. look at each element of the array (i.e. cPtr[x]),   
2. convert it to an integer (i.e. (int) cPtr[x])   
3. use a 256 element look-up table to see how many bits are set in the given byte (i.e. cPtr[x]). 

我突然想到，如果我使用短int指针（即短int*sPtr），那么我只需要一半的查找次数，但需要一个65534元素的查找表，这将有其自身的内存使用成本。

我想知道每次检查的最佳位数是多少。此外，如果该数字不是某个预设类型的大小，我如何沿着位向量向下走，并将指针设置为超过位数组起始位置的ANY任意位数。

我知道还有其他方法可以计数比特，但现在我想确定在与其他方法进行比较之前，我可以优化这个方法。

Answer 1

您可以使用按位操作进行计数：

char c = cPtr[x];
int num = ((c & 0x01) >> 0) +
          ((c & 0x02) >> 1) +
          ((c & 0x04) >> 2) +
          ((c & 0x08) >> 3) +
          ((c & 0x10) >> 4) +
          ((c & 0x20) >> 5) +
          ((c & 0x40) >> 6) +
          ((c & 0x80) >> 7);

它可能看起来有点长，但它不需要访问太多时间来访问内存，所以毕竟它对我来说似乎很便宜

您甚至可以通过每次读取int来降低成本，但随后可能需要解决对齐问题。

Answer 2

我想知道每次检查的最佳位数是多少

找到答案的唯一方法就是测试。有关一次计数32位的最快方法的讨论，请参阅此问题。

此外，如果这个数字不是某个预设类型的大小，我怎么能向下遍历我的位向量，并将指针设置为任意数字超过位阵列的起始位置的位的数目。

不能将指针设置为任意位。大多数机器都有字节寻址，有些只能寻址单词。

您可以构造一个以任意位开头的单词，如：

long wordAtBit(int32_t* array, size_t bit)
{
    size_t idx = bit>>5;
    long word = array[idx] >> (bit&31);
    return word | (array[idx+1] << (32 - (bit&31));
}

Answer 3

这应该很快（取自维基百科）：

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount(uint32 i)
{
    return (wordbits[i&0xFFFF] + wordbits[i>>16]);
}

通过这种方式，每次迭代可以检查32位。

Answer 4

我参加聚会有点晚了，但有比迄今为止建议的更快的方法。原因是许多现代体系结构提供了硬件指令，以各种方式计数位数（前导零、前导一、尾随零或一、计数设置为1的位数等）。计数设置为0的位数被称为Hamming权重，也称为总体计数，或仅为popcount。

事实上，x86 CPU有一条POPCNT指令作为SSE4.2指令集的一部分。英特尔最新的CPU架构（昵称Haswell）通过BMI1和BMI2扩展为位操作提供了更多的硬件支持——也许还有其他东西可以使用！