Last day when I was working through some code for decrypting a cipher text, it was required to count the number of 1’s in the binary representation of unsigned int. It appears as if it’s a simple issue where all you have to do is some thing like this:-
int count_bits(unsigned int num)
{
int count = 0;
while(num)
{
if(num % 2)
count++;
num /= 2;
}
return count;
}
But since I had to make this function call many times in my program (through thousands of cipher characters) the application tend to slow down. The problem was that the function involved good number of branching (loops), and as we know branching requires good amount of system cycles. On searching through various threads in technical forums I learned that this above mentioned bit counting function had a name of its own,’ population function’ and the best way to deal with the inefficiency of a population function is to makes use of Look up tables. The looks up tables are efficient because of the fact that data fetching requires less system cycles in comparison to branching. For the above mentioned problem I will create a look up table bite_count [255] giving the number of one bits set in each possible byte value. We then use this table to find the number of ones in each byte of the integer and add up the results. With no branches, four memory accesses, and almost no arithmetic, the population function can be created as follows:-
int count_ones(unsigned int x)
{
return bits_set[x & 255] + bits_set[(x >> 8 ) & 255] +
bits_set[(x >> 16) & 255] + bits_set[(x >> 24) & 255];
}
