Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
899 views
in Technique[技术] by (71.8m points)

language agnostic - How many 1s in an n-bit integer?

An interesting problem I ran into today: what is the fastest way to count the number of 1s in an n-bit integer? Is it possible to beat O(n)?

For example:

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

Clearly, the naive algorithm is to simply count. But, are there any tricks to speed it up?

(This is merely an academic question; there is no expected performance gain by implementing such a strategy.)

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

See the fabulous Bit Twiddling Hacks article.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...