Home > Applied Algorithms, Bit Manipulation > Counting number of valid zeros in binary representation of a number

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?! 🙂

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: