Count total set bits in all numbers from 1 to n |  ; ans store sum of set bits from 0 to n ; while n greater than equal to 2 ^ i ; This k will get flipped after 2 ^ i iterations ; change is iterator from 2 ^ i to 1 ; This will loop from 0 to n for every bit position ; When change = 1 flip the bit ; again set change to 2 ^ i ; increment the position ; Main Function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSetBits ( int n ) { int i = 0 ; int ans = 0 ; while ( ( 1 << i ) <= n ) { bool k = 0 ; int change = 1 << i ; for ( int j = 0 ; j <= n ; j ++ ) { ans += k ; if ( change == 1 ) { k = ! k ; change = 1 << i ; } else { change -- ; } } i ++ ; } return ans ; } int main ( ) { int n = 17 ; cout << countSetBits ( n ) << endl ; return 0 ; }