## Counting number of valid zeros in binary representation of a number

This one is actually a question suggested by a dear friend. And a pretty neat one. What we need is to find out the number of *valid* zeros in the binary representation of a number. Valid zeros would be those who have atleast one 1 to their left.

For example, 000010101 (13 in decimal) has only 2 valid zeros. People might go on to solve this in different ways. Some might find the binary representation of the number and literally count the valid 0s. They might use comparitively complex things such as bitset (STL) for this or even strings.

However, the correct (read best) way to solving this is pretty simple and utilizes Bit Manipulations. You just keep finding if the* least significant bit (LSB)* is 0 till the time the *number* isn’t zero. I’ll write a simple pseudo-code for this,

int count=0;

int mask=1;

while ( INPUT_NUMBER ) //till number doesn’t become zero

{

if (INPUT_NUMBER & mask == 0) //checking if LSB is 0

{

count++;

}

INPUT_NUMBER = INPUT_NUMBER>>1; //right shifting by 1 to get next bit

}

Woah! That was a simple one. And damn efficient at that. Do you now realize how simple things can become with bit manipulations?! 🙂