Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
2
To be clear, every piece of information is stored as binary in computers. So integer values are no exception. For e.g. 4 is stored as 100, 27 is stored as 11011 etc. 4 has only one on bit where as 27 has 4.
The first algorithm that comes to mind is, iterate through the entire number examining each bit at a time and increment a counter i.e.
int main()
{
int num;
int count = 0;
printf("Please enter a number - ");
scanf("%d", &num);
while (num > 0)
{
if(num & 01 == true) // if right most bit is on
count++;
num >>= 1; // or num /=2 (divide num by 2 and it becomes the next num
}
printf("On bit Count is : %d\n", count);
return 0;
}
How long this function takes. Since at max we traverse total number of bits in the given variable (32 bit or 64 bit depending upon size of integer), we can state that as O(32) or O(64). If it needs to computed in terms of number i.e. num which is input, it would be log(num). The reason is number of bits needed to represent a number is always the log of that number.
Is there are way to improve it? To some extent – yes.
I wrote a previous tutorial describing a faster method to compute power of 2. The same property applies here. To explain, here are some examples
27 – Binary 011111. There are 5 on bits. Now if we do 27 & (27-1)
011111 // 27
011110 // 26
011110 // Right most on bit is removed
If we keep doing it every time the right most on bit (no matter where it exists is removed until the number becomes zero. So using this strategy we can compute number of on bits in exactly the same number of iterations. i.e. if there is no on bit we determine that in one iteration, if 5 on bits we need 5 iterations, if n, we need n iterations. So complexity would be
O(num of on bits)
which is always less than (or at worst equal to) earlier complexity of number of bits.
Here is the code change in the while loop above
while (num > 0)
{
num &= (num-1);
count++;
}
Back to top
