Hamming weight
Intro
Let's assume that we have a binary number and we want to find the number of bits that are '1'. This is also known as the hamming weight of the number.
Method 1
One way to do this is illustrated bellow (taken from a friend's code):
int cnz(unsigned long ul) { int nrbits = 0; for (;;){ if (!ul) break; ul &= (ul -1); nrbits++; } return nrbits; }
This algorithm takes advantage of the fact that the (ul-1) operation reverses all the bits of the ul until (and including) the first '1' reached starting from the end. Using this algorithm we need a number of steps equal to the number of '1'.
Method 2
Linux kernel on the other hand uses the following method (assuming for our example that the size of our number is 32 bits):
unsigned int generic_hweight32(unsigned int w) { unsigned int res = w; res = (res & 0x55555555) + ((res >> 1) & 0x55555555); res = (res & 0x33333333) + ((res >> 2) & 0x33333333); res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F); res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF); res = (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF); return res; }
Note that:
0x55555555 is 01010101010101010101010101010101 0x33333333 is 00110011001100110011001100110011 0x0F0F0F0F is 00001111000011110000111100001111 0x00FF00FF is 00000000111111110000000011111111 0x0000FFFF is 00000000000000001111111111111111
This method is based on the principle of divide and conquer. Given that our initial number is represented as: a_{0}a_{1}a_{2}...a_{31} It works like this:
- step 1: a_{0}a_{1} = a_{0} + a_{1} ... a_{30}a_{31} = a_{30} + a_{31}
- step 2: a_{0}a_{1}a_{2}a_{3} = a_{0}a_{1} + a_{2}a_{3} ... a_{28}a_{29}a_{30}a_{31} = a_{28}a_{29} + a_{30}a_{31}
- ...
- step 5 : a_{0}...a_{31} = a_{0}...a_{15}+a_{16}...a_{32}
Note that the steps of the algorithm are log_{2}(total_nr_bits) for the general case.