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
def countSetBits ( n ) : NEW_LINE INDENT i = 0 NEW_LINE ans = 0 NEW_LINE while ( ( 1 << i ) <= n ) : NEW_LINE INDENT k = 0 NEW_LINE change = 1 << i NEW_LINE for j in range ( 0 , n + 1 ) : NEW_LINE INDENT ans += k NEW_LINE if change == 1 : NEW_LINE INDENT k = not k NEW_LINE change = 1 << i NEW_LINE DEDENT else : NEW_LINE INDENT change -= 1 NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 17 NEW_LINE print ( countSetBits ( n ) ) NEW_LINE DEDENT