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

n位整数中有多少个1?

bit-manipulation language-agnostic

carl · 技术社区 · 15 年前

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

例如:

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

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

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

5 回复 | 直到 15 年前

Ates Goral 15 年前

bdonlan 15 年前

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

On Freund 15 年前

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

Martin Beckett 15 年前

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

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

starblue 15 年前

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

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

推荐文章

no one special · 32位整数缩放,无溢出

6 年前

calebeja9 · c理解中的逻辑转换

6 年前

Benn Tan · 比特操作:更难翻动硬币

6 年前

Ganesh Thampi · 使用位运算符将十进制转换为二进制

6 年前

Ganesh Thampi · 使用位的奇偶程序

6 年前

datapanda · 三维网格的莫顿反向编码

6 年前

rubyquartz · 交换无符号短整数的字节

6 年前

John Proctor · C中位的掩蔽范围

6 年前

Areg Sarvazyan · 从无符号int中提取位的函数

6 年前

user9505617 · 按位异或0xFFFFFFFF?

6 年前