# RANDOMIZED ALGORITHMS 2

QUESTION

Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.

``````// 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;
}`````` #### Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker. 