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.

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

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

Powered By
CHP Adblock Detector Plugin | Codehelppro