14

我知道如何找出给定数字中有多少位（或布尔数组中有多少元素为真），使用掩码和按位运算符，检查所有位是否打开。假设数字是任意长度，算法在 O(n) 时间内运行，其中 n 是数字中的位数。有没有渐近更好的算法？我不认为这是可能的，但我怎样才能正式证明呢？

4

7 回答 7

23

Bit Twiddling Hacks提出了许多方法，包括这个：

计数位设置，Brian Kernighan 的方式

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Brian Kernighan 的方法经历了与设置位一样多的迭代。因此，如果我们有一个仅设置了高位的 32 位字，那么它只会通过循环一次。

实际算法示例：

128 == 10000000 2 , 1 位设置

128 & 127 ==   0    10000000 & 01111111 == 00000000

177 == 10110001 2 , 4 位设置

177 & 176 == 176    10110001 & 10110000 == 10110000
176 & 175 == 160    10110000 & 10101111 == 10100000
160 & 159 == 128    10100000 & 10011111 == 10000000
128 & 127 ==   0    10000000 & 01111111 == 00000000

255 == 11111111 2 , 8 位设置

255 & 254 == 254    11111111 & 11111110 == 11111110
254 & 253 == 252    11111110 & 11111101 == 11111100
252 & 251 == 248    11111100 & 11111011 == 11111000
248 & 247 == 240    11111000 & 11110111 == 11110000
240 & 239 == 224    11110000 & 11101111 == 11100000
224 & 223 == 192    11100000 & 11011111 == 11000000
192 & 191 == 128    11000000 & 10111111 == 10000000
128 & 127 ==   0    10000000 & 01111111 == 00000000

至于算法复杂性的语言不可知问题，不可能比 O( n ) 做得更好，其中n是位数。任何算法都必须检查一个数字中的所有位。

棘手的是，当您对n的定义不小心时，让n成为“位移/屏蔽指令的数量”或类似的东西。如果n是位数，那么即使是简单的位掩码 ( &) 也已经是 O( n ) 操作。

那么，这可以在比 O( n ) 位测试更好的情况下完成吗？不可以。
它可以在少于 O( n ) 的添加/移位/掩码操作中完成吗？是的。

于 2012-12-11T15:47:18.957 回答
7

我总是用这个：

int
count_bits(uint32_t v)
{
        v = v - ((v >> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        return ((v + (v >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
}

你必须知道你的整数的大小。

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

于 2012-12-11T15:51:34.777 回答
4

Brian Kerninghan's algorithm to count 1-bits.

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Read this and other bit-twiddling hacks here: Bit-twiddling hacks.

于 2012-12-11T15:49:32.373 回答
3

进行此计算的最快方法是使用表数组 edx[bl]，其中 bl 寄存器包含一个字节值。如果数字是单字节，那么答案是一条指令：

 mov eax, [edx:bl]

如果数字中有很多字节（例如 ebp 指向的数组），则循环遍历字节（其中 ecx 是包含数字的数组中的字节数）：

    sub ecx, 1
    mov eax, 0
 DoNextByte:
    mov bl, [ebp:ecx]
    add eax, [edx:bl]
    test ecx, ecx
    jz Done:
    sub ecx, 1
    jmp DoNextByte:
 Done:
    ; answer is in eax

这是绝对最快的方法，并且比任何数学计算都要快。请注意，Art 解决方案中的移位指令非常耗费 CPU。

Kernighan 解决方案的问题在于，即使在汇编中手动编码，它也比我的算法慢。如果它是用 C 编译的，它可能会产生大量的内存访问，这会减慢它的速度，甚至超出它所需的大量时钟周期。

请注意，如果字节到计数的映射在该指令旁边内联，那么整个数据表将在 CPU 缓存中，因此它会非常快。在这种情况下，甚至没有 C 程序可以接近（想想慢 20 倍或更多）。

于 2012-12-11T20:19:24.063 回答
1

我认为您正在寻找的形式类型是“对抗性证明”。

假设一个算法 A 的运行速度比 O(n) 快。那么对于足够大的 n，A 不能查看某个位 i。然后我们声称 A 一定是不正确的。“对手”将给 A 两个字符串 s1 和 s2，除了位 i 的相反值外，它们是相同的。算法 A 将为 s1 和 s2 返回相同的值，因此对手“欺骗”了 A 给出错误的答案。因此不存在在 o(n) 时间内运行的正确算法 A。

于 2013-01-22T06:30:06.770 回答
1

好吧，您还可以使用查找表来保存每个字节的#bits，然后将数字分成字节，将查找值相加。

它仍然是 O（位数），但系数很小。

于 2012-12-11T19:12:23.317 回答
0

好的，这里似乎对顺序统计、渐近符号、“大 O”有些混淆。

Brian Kernighan 的算法在操作数方面更好，这是正确的。然而，渐近更好是不正确的。

这可以从big-O 的定义中看出。

回想一下，根据定义，当存在函数g(n)使得当n变得足够大时f(n) ≤ kg(n)时，函数是O(f(n)) 。

现在，让我们将w定义为在字中设置的位数，并进一步注意单个字的运行时间，如上面所观察到的，是设置的位数的函数。调用该函数c(w)。我们知道有一个固定的字宽，叫它ww；显然对于任何单词， 0 ≤ c(w) ≤ ww，当然，最坏的情况是c(w) = c(ww)。所以，这个算法的运行时间，最坏的情况是nc(ww)。

因此，对于n，运行时间为 ≤ nc(ww)；也就是说，n ≤ nc(ww)，因此根据定义，该算法具有 O(n) 的渐近最坏情况运行时间。

于 2013-01-03T20:56:42.633 回答