Monday, August 31, 2009

Bit counting (how many 1's in 5 [binary])

This code is simple and can be enhanced to work in more general cases. If you do end up changing any of the code and wish to post it, please feel free to do, but, do post a link back to this site.

Since so many of you have had problems in interviews regarding bit counting, I have decided to post this program. It counts the amount of 1's that there are in any 32 bit number.



#include <stdio.h>

#define BIT_MASK 0x1

int main()
{
int number = 52;
int i = 0;
int counter=0;
/*Looping for each bit in an int.*/
for(i = 0; i < 32; i++)
{
/*
RF1 -> Shift to the right by 1
52 is 110100 in binary.
Bitwise AND 0 with 1 ---> 0 -> RF1
0 with 1 ---> 0 -> RF1
1 with 1 ---> 1 increase counter -> RF1
0 with 1 ---> 0 -> RF1
1 with 1 ---> 1 increase counter -> RF1
1 with 1 ---> 1 increase counter -> RF1
...
It will continue 32 times except that
in this case (52) the rest will be 0s.
*/
if(number & BIT_MASK)
counter++;
number = number >> 1;
}


printf("The number of 1's in %d is: %d", number, counter);
/* Visual Studio will close the output window very fast.
This trick will keep it open.
*/
getchar();

}

No comments: