查找数字中有多少位

Question

我知道如何使用掩码和按位运算符找出给定数字中有多少位(或者在布尔arra中有多少个元素),检查它们是否打开时检查所有位.假设该数字具有任意长度,则该算法在O(n)时间内运行,其中n是该数字中的位数.是否有渐近更好的算法？我不认为这是可能的,但我怎么能正式证明呢？

Answer 1

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 ₂,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 ₂,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(完成ñ)添加/移位/屏蔽操作？是.

Answer 2

我一直用这个:

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

Answer 3

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

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