Count total set bits in all numbers from 1 to n | Set 2 | Function to return the sum of the count of set bits in the integers from 1 to n ; Ignore 0 as all the bits are unset ; To store the powers of 2 ; To store the result , it is initialized with n / 2 because the count of set least significant bits in the integers from 1 to n is n / 2 ; Loop for every bit required to represent n ; Total count of pairs of 0 s and 1 s ; totalPairs / 2 gives the complete count of the pairs of 1 s Multiplying it with the current power of 2 will give the count of 1 s in the current bit ; If the count of pairs was odd then add the remaining 1 s which could not be groupped together ; Next power of 2 ; Return the result ; Driver code
def countSetBits ( n ) : NEW_LINE INDENT n += 1 ; NEW_LINE powerOf2 = 2 ; NEW_LINE cnt = n // 2 ; NEW_LINE while ( powerOf2 <= n ) : NEW_LINE INDENT totalPairs = n // powerOf2 ; NEW_LINE cnt += ( totalPairs // 2 ) * powerOf2 ; NEW_LINE if ( totalPairs & 1 ) : NEW_LINE INDENT cnt += ( n % powerOf2 ) NEW_LINE DEDENT else : NEW_LINE INDENT cnt += 0 NEW_LINE DEDENT powerOf2 <<= 1 ; NEW_LINE DEDENT return cnt ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 14 ; NEW_LINE print ( countSetBits ( n ) ) ; NEW_LINE DEDENT