QUESTION
Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.
ANSWER
// A simple program to count set bits
// in all numbers from 1 to n.
#include <stdio.h>
// A utility function to count set bits
// in a number x
unsigned int countSetBitsUtil(unsigned int x);
// Returns count of set bits present in all
// numbers from 1 to n
unsigned int countSetBits(unsigned int n)
{
int bitCount = 0; // initialize the result
int i;
for (i = 1; i <= n; i++)
bitCount += countSetBitsUtil(i);
return bitCount;
}
// A utility function to count set bits
// in a number x
unsigned int countSetBitsUtil(unsigned int x)
{
if (x <= 0)
return 0;
return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2);
}
// Driver program to test above functions
int main()
{
// int n = 8;
int n;
scanf("%d",&n);
printf("Total set bit count is %d", countSetBits(n));
return 0;
}