1

我想计算在一个非常大的位向量（即 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]).

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

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

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

4

4 回答 4

2

您可以使用按位运算对其进行计数：

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 来降低成本，但是您可能需要解决对齐问题。

于 2012-03-05T21:22:19.050 回答
1

这应该很快（取自Wikipedia）：

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 位。

于 2012-03-05T21:22:33.760 回答
1

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

找出答案的唯一方法是测试。有关一次计算 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));
}
于 2012-03-05T21:58:49.680 回答
0

我参加聚会有点晚了，但是有比迄今为止建议的方法更快的方法。原因是许多现代架构提供硬件指令以各种方式计算位数（前导零、前导 1、尾随 0 或 1、计算设置为 1 的位数等）。计算设置为 1 的位数称为汉明权重，通常也称为人口数，或简称为人口数。

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

于 2013-08-18T21:30:56.503 回答