多少1秒中的n位整数？ [英] How many 1s in an n-bit integer?

问题描述

这是有趣的问题，我今天碰见：什么是计算在n位整数中1的个数最快的方法？是否有可能击败O（N）？

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)?

例如：

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.)

推荐答案

请参阅神话般位操作黑客的文章

这篇关于多少1秒中的n位整数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！