asked on

How to compute the number of ones in a 32 bit integer ?

Hi Folks
I am trying to figure out how to parallelly compute the number of bits. The solution from the Stanford site is as follows :

Counting bits set, in parallel

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];

The B array, expressed as binary, is:

B[0] = 0x55555555 = 01010101 01010101 01010101 01010101
B[1] = 0x33333333 = 00110011 00110011 00110011 00110011
B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111
B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111
B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111

I am actually having trouble to decipher it, if any one can you explain it
it would be great.
Thanks for the help.

-H

ozo

c = v - ((v >> 1) & B[0]);
count the number of bits in each pair
c = ((c >> S[1]) & B[1]) + (c & B[1]);
count the number of bits in each nybble
c = ((c >> S[2]) + c) & B[2];
count the number of bits in each byte
c = ((c >> S[3]) + c) & B[3];
count the number of bits in each 16 bit word
c = ((c >> S[4]) + c) & B[4];
count the number of bits in each 32 bit word

HukkaHua

ASKER

ozo , v - ((v >> 1) & B[0]);
how does this statement work ?

divide it by 2 , so I have shifted everythng to the right
and B[0] all have alternating ones...such that it masks all
the ones in the shifted v , but how does the subtract work after that ?

Thanks
H

ASKER CERTIFIED SOLUTION

Kent Olsen

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

HukkaHua

ASKER

Hi Kent,
I am really thankful to you for taking the time and providing the insight to the working of this algorithm without which it would have never hit my mind. One of the most thorough replies that I have got in this site.

Please bear with me and could you further explain why the second line

c = ((c >> S[1]) & B[1]) + (c & B[1]);

is this and the third line is

c = ((c >> S[2]) + c) & B[2];

I at least understood a little bit of the algorithm.

Thanks to you again.

Regards,
-H

SOLUTION

ozo

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

ozo

the third step takes a short cut and does a single mask operation on the sum, instead of separate mask operation on each piece, because it is known that the sum will not overflow the into the next piece.