Count total set bits in all numbers from 1 to n | Function which counts set bits from 0 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 ; Driver code
< ? php function countSetBits ( $ n ) { $ i = 0 ; $ ans = 0 ; while ( ( 1 << $ i ) <= $ n ) { $ k = 0 ; $ change = 1 << $ i ; for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) { $ ans += $ k ; if ( $ change == 1 ) { $ k = ! $ k ; $ change = 1 << $ i ; } else { $ change -- ; } } $ i ++ ; } return $ ans ; } $ n = 17 ; echo ( countSetBits ( $ n ) ) ; ? >