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