相关疑难解决方法(0)

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

例如:

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

显然,天真算法只是简单计算.但是,有什么技巧可以加快速度吗？

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