以二进制表示计数 1 的个数 [英] Count number of 1's in binary representation

问题描述

如果您有足够的内存可以使用，那么在 O(1) 中计算数字的二进制表示中 1 的数量的有效方法.这是我在一个在线论坛上找到的一个面试问题，但没有答案.有人可以提出一些建议吗，我想不出一种在 O(1) 时间内完成的方法?

Efficient way to count number of 1s in the binary representation of a number in O(1) if you have enough memory to play with. This is an interview question I found on an online forum, but it had no answer. Can somebody suggest something, I cant think of a way to do it in O(1) time?

推荐答案

这就是 汉明权重问题，也就是人口统计.该链接提到了有效的实现.引用:

That's the Hamming weight problem, a.k.a. population count. The link mentions efficient implementations. Quoting:

有了无限的内存，我们可以简单地创建一个每个 64 位整数的汉明权重的大型查找表

With unlimited memory, we could simply create a large lookup table of the Hamming weight of every 64 bit integer

这篇关于以二进制表示计数 1 的个数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！