代码之家 › 专栏 › 技术社区 › carl

n位整数中有多少个1?

bit-manipulation language-agnostic

4

carl · 技术社区 · 16 年前

今天我遇到了一个有趣的问题:在一个n位整数中,计算1s的最快方法是什么?能打败O(N)吗?

例如:

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

显然,幼稚的算法只是简单的计数。但是,有什么办法可以加快速度吗?

(这仅仅是一个学术问题;实施这样一个战略并没有预期的业绩增长。)

5 回复 | 直到 16 年前

1

17

Ates Goral 16 年前

2

4

bdonlan 16 年前

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

3

On Freund 16 年前

最快的方法(不使用特殊的处理器功能或存储预先计算的答案)是将值-1循环到0。迭代次数是1的次数。

4

2

Martin Beckett 16 年前

如果有有限的位(例如32位),可以预先计算它,然后在数组中查找值。

一种更实用的方法是对每个字节或字执行此操作(只占用256/64K字节),然后将每个字节/字的结果添加到值中。

5

0

starblue 16 年前

O(log n) ,如果您不超越机器字,忽略每个机器操作都在n位上运行的事实。

在实践中,您应该使用库函数,而不是自行删除这些位,例如Java中的整数.BITCONTUTE()。