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₀a₁a₂...a₃₁ It works like this:

• step 1: a₀a₁ = a₀ + a₁ ... a₃₀a₃₁ = a₃₀ + a₃₁
• step 2: a₀a₁a₂a₃ = a₀a₁ + a₂a₃ ... a₂₈a₂₉a₃₀a₃₁ = a₂₈a₂₉ + a₃₀a₃₁
• ...
• step 5 : a₀...a₃₁ = a₀...a₁₅+a₁₆...a₃₂

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