n位整数中有多少1？

Question

我今天遇到的一个有趣的问题：在n位整数中计算1的数量的最快方法是什么？是否有可能击败O（n）？

例如：

42 = 0b101010 => 3 ones
512 = 0b1000000000 => 1 one

显然，天真算法只是简单计算。但是，加速它有什么技巧吗？

（这仅仅是一个学术问题;通过实施这样的策略没有预期的性能提升。）

Answer 1

请参阅精彩的 Bit Twiddling Hacks文章。

Answer 2

x86处理器上最快的方法可能是使用 POPCNT 指令类。

Answer 3

最快的方式（不使用特殊的处理器功能或存储预先计算的答案）是在一个循环中将值与值-1进行比较，直到它为0.迭代次数是1的次数。

Answer 4

如果你有一个有限数量的位（例如32位），你可以预先计算它，然后只需查找数组中的值。

稍微更实际的方法是对每个字节或字执行此操作（仅需要256 / 64k字节），然后为值中的每个字节/字添加结果

Answer 5

O（log n），如果你不去超出机器词并忽略每个机器操作在n位上运行的事实。

在实践中，您应该使用库函数而不是自己编写这些位，例如Java中的Integer.bitCount（）。