troubleshooting Question

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

asked on
CAlgorithms
6 Comments1 Solution1003 ViewsLast Modified:
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);
c = ((c >> S) & B) + (c & B);
c = ((c >> S) + c) & B;
c = ((c >> S) + c) & B;
c = ((c >> S) + c) & B;

The B array, expressed as binary, is:

B = 0x55555555 = 01010101 01010101 01010101 01010101
B = 0x33333333 = 00110011 00110011 00110011 00110011
B = 0x0F0F0F0F = 00001111 00001111 00001111 00001111
B = 0x00FF00FF = 00000000 11111111 00000000 11111111
B = 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
Join the community to see this answer!
Join our exclusive community to see this answer & millions of others.
Unlock 1 Answer and 6 Comments.
###### Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 6 Comments.

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.