c - C 中的位旋转 - 计算位

Question

我想计算在一个非常大的位 vector (即 100,000 位)中设置的位。

我目前正在做的是使用指向 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]). 

我突然想到，如果我改用 short int 指针(即 short int * sPtr)，那么我只需要一半的查找次数，但有一个 65534 元素的查找表，它将有它的自己的内存使用成本。

我想知道每次检查的最佳位数是多少。此外，如果该数字不是某些预设类型的大小，我如何沿着我的位 vector 向下移动并将指针设置为 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 来降低成本，但是您可能需要解决对齐问题。