n 位整数中有多少个 1？
今天遇到一个有趣的问题：计算 n 位整数中 1 的数量最快的方法是什么？有可能击败 O(n) 吗？
例如：
42 = 0b101010 => 3 ones
512 = 0b1000000000 => 1 one
显然，简单的算法就是简单地计数。但是，有什么技巧可以加快速度吗？
（这只是一个学术问题；实施这样的策略不会带来预期的性能提升。）
An interesting problem I ran into today: what is the fastest way to count the number of 1s in an n-bit integer? Is it possible to beat O(n)?
For example:
42 = 0b101010 => 3 ones
512 = 0b1000000000 => 1 one
Clearly, the naive algorithm is to simply count. But, are there any tricks to speed it up?
(This is merely an academic question; there is no expected performance gain by implementing such a strategy.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
请参阅精彩的Bit Twiddling Hacks 文章。
See the fabulous Bit Twiddling Hacks article.
x86 处理器上最快的方法可能是使用 POPCNT 指令类。
Probably the fastest way on x86 processors would be to use the POPCNT class of instructions.
最快的方法（不使用特殊的处理器功能或存储预先计算的答案）是在循环中将您的值与值 - 1 进行 AND 运算，直到其为 0。迭代次数就是 1 的数量。
The fastest way (without using special processor features or storing pre-calculated answers) is to AND your value with value - 1 in a loop until it's 0. The number of iterations is the number of 1's.
如果您的位数有限（例如 32 位），您可以预先计算它，然后在数组中查找该值。
稍微更实用的方法是对每个字节或字执行此操作（仅需要 256/64k 字节），然后将每个字节/字的结果添加到值中
If you have a finite number of bits (eg 32 bits) you can precalcualte it and then just look up the value in an array.
A slightly more practical way is to do this for each byte or word (only takes 256/64k bytes) and then add the results for each byte/word in the value
O(log n)，如果你不超越机器字并忽略每个机器操作都在 n 位上运行的事实。
在实践中，您应该使用库函数，而不是自己摆弄这些位，例如 Java 中的 Integer.bitCount()。
O(log n), if you don't go beyond machine words and disregard the fact that each machine operation operates on n bits.
In practice you should use library functions instead of twiddling the bits yourself, for example Integer.bitCount() in Java.