代码之家 › 专栏 › 技术社区 › 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()。

推荐文章

John V · 是否存在单元测试无法发现的逻辑/流错误类型?

7 年前

Beefster · 为什么ANSI颜色转义以“m”而不是“]”结尾?

7 年前

Guillermo Gutiérrez · STR转换是如何工作的?

7 年前

RudziankoÅ · 合并排序数组算法

7 年前

user8852560 · 构造函数中的验证和构造函数冲突

7 年前

SuperHeroY · 在大于8x8的棋盘上进行象棋移动验证?[已关闭]

7 年前

jav974 · 订购产品时寻找最佳价格组合的算法

7 年前

hippietrail · 确定浮点数中前导零的数量

7 年前

Will Da Silva Alex Martelli · 如何确定具有s边的多边形的数字是否为多边形

7 年前

LaoJiu · 为什么在文本编辑器的查找函数中选择“BM算法”而不是“周日算法”?

7 年前