Why is it useful to count the number of bits?

Question

I've seen the numerous questions about counting the number of set bits in an insert type of input, but why is it useful?

For those looking for algorithms about bit counting, look here:

1. Counting common bits in a sequence of unsigned longs
2. Fastest way to count number of bit transitions in an unsigned int
3. How to count the number of set bits in a 32-bit integer?

Mulatto

Answer 1

You can regard a string of bits as a set, with a 1 representing membership of the set for the corresponding element. The bit count therefore gives you the population count of the set.

Practical applications include compression, cryptography and error-correcting codes. See e.g. wikipedia.org/wiki/Hamming_weight and wikipedia.org/wiki/Hamming_distance.

Muster

Answer 2

If you're rolling your own parity scheme, you might want to count the number of bits. (In general, of course, I'd rather use somebody else's.) If you're emulating an old computer and want to keep track of how fast it would have run on the original, some had multiplication instructions whose speed varied with the number of 1 bits.

I can't think of any time I've wanted to do it over the past ten years or so, so I suspect this is more of a programming exercise than a practical need.

Schmo

You can calculate parity directly with fewer operations than for a population count (unless your CPU has POPCNT or similar). – Muster

Answer 3

In an ironic sort of fashion, it's useful for an interview question because it requires some detailed low-level thinking and doesn't seem to be taught as a standard algorithm in comp sci courses.

Fraudulent

Answer 4

Some people like to use bitmaps to indicate presence/absence of "stuff".

There's a simple hack to isolate the least-significant 1 bit in a word, convert it to a field of ones in the bits below it, and then you can find the bit number by counting the 1-bits.

countbits((x XOR (x-1)))-1;

Watch it work.

Let x =     00101100
Then x-1 =  00101011
x XOR x-1 = 00000111

Which has 3 bits set, so bit 2 was the least-significant 1-bit in the original word

Circumstantiate