## 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: a0a1a2...a31 It works like this:

• step 1: a0a1 = a0 + a1 ... a30a31 = a30 + a31
• step 2: a0a1a2a3 = a0a1 + a2a3 ... a28a29a30a31 = a28a29 + a30a31
• ...
• step 5 : a0...a31 = a0...a15+a16...a32

Note that the steps of the algorithm are log2(total_nr_bits) for the general case.