ansaurus

Question

Answer 1

+2 A:

If you have a finite number of bits (eg 32 bits) you can precalcualte it and then just look up the value in an array.

A slightly more practical way is to do this for each byte or word (only takes 256/64k bytes) and then add the results for each byte/word in the value

Martin Beckett 2009-10-23 04:13:01

Except it would be hard with 32 bits… Assuming you used 1 bit per value… Would require 512 megs of storage :( Byte/word precalculation would be better.

David Wolever 2009-10-23 04:27:45

David, you can't have 1 bit per value if you need to store a bitcount from 0 through 32 inclusive so it's worse than that.

paxdiablo 2009-10-23 04:32:04

Works pretty well 8 or 16 bits at a time though.

hobbs 2009-10-23 05:45:18

Answer 2

+16 A:

See the fabulous Bit Twiddling Hacks article.

Ates Goral 2009-10-23 04:13:02

+1 excellent reference for this sort of thing.

Stephen Canon 2009-10-23 04:19:36

Great article - thanks very much.

carl 2009-10-23 04:24:37

You're welcome. We should thank Delicious and its bookmark tagging capability for allowing me to pull out the link in a jiffy!

Ates Goral 2009-10-23 04:46:31

Answer 3

+4 A:

Probably the fastest way on x86 processors would be to use the POPCNT class of instructions.

bdonlan 2009-10-23 04:14:46

If they have POPCNT, that is; only the most recent Intel processors do.

Stephen Canon 2009-10-23 04:18:31

Answer 4

+3 A:

The fastest way (without using special processor features or storing pre-calculated answers) is to AND your value with value - 1 in a loop until it's 0. The number of iterations is the number of 1's.

On Freund 2009-10-23 04:15:49

You mean 2^n, don't you?

Basilevs 2009-10-23 04:40:33

I'm not sure I follow. Where do you think I mean 2^n?

On Freund 2009-10-23 04:45:08

This is only "the fastest way" when you know that the number of 1 is low. If the number of 1's is high, this method becomes extremely slow. The best way of solving this problem by actually *counting* the 1's is the well-known shift-and-add method that does the job in `log n` operations guaranteed. (Of course, in practice a byte-wise table-based method might prove the best, which is probably what you call "pre-calculating")

AndreyT 2009-10-23 05:31:56

Actually, this algorithm's worst case running time is log n, just like the constant running time of the naive approach. As I mentioned in my answer, the number of iterations equals the number of 1's, and since there cannot be more than log n 1's, and each iteration takes constant time, the running time cannot be more than log n.

On Freund 2009-10-23 05:46:16

@On Freund: You missed the fact that in this thread `n` stands for the number of bits in the number (see the OP), not for the number itself. Your algorithm takes O(n) time, while shift-and-add approach takes O(log n).

AndreyT 2009-10-23 06:41:53

If you refer to the number of bits as n, then your approach (shift and add) will take O(n) just like mine. How exactly do you achieve lower running time than O(n) with shift and add? You need n shifts...

On Freund 2009-10-23 07:50:53

@On Freund: By shift-and-add I meant not the "naive" approach, but rather the "Counting bits set, in parallel" approach from here http://graphics.stanford.edu/~seander/bithacks.html

AndreyT 2009-10-23 08:31:02

"Counting bits set, in parallel" does use pre-calculation, namely the B array.

On Freund 2009-10-23 08:45:02

@On Freund: No. The `B` array is just a bunch of bit masks. There's absolutely no reason to store these flags in an array, just like there's no reason to store shifts in `S` array. I don't know why they did it this way. To call this "pre-calculation" is the same as to call constants `-1` and `0` in your solutuioin as "pre-calculation".

AndreyT 2009-10-23 16:41:04

The size of the storage for the bit masks (be it an array or anything else) depends on n (O(n*logn)), quite a difference from the two constants in "my" solution.Calling B "just a bunch of bit masks" is equivalent to calling the lookup table "just a bunch of numbers".

On Freund 2009-10-23 18:44:11

Answer 5

A:

Just a link for a method posted on gowrikumar.com

bbg 2009-10-23 05:24:33

Answer 6

A:

O(log n), if you don't go beyond machine words and disregard the fact that each machine operation operates on n bits.

In practice you should use library functions instead of twiddling the bits yourself, for example Integer.bitCount() in Java.

starblue 2009-10-23 07:09:56

ansaurus

tags:

views:

answers:

How many 1s in an n-bit integer?

related questions