question find the sum of number of set bits in all the numbers in the range 1 n consider a number x and half of the number x2 the binary representation of x has all the digits as the binary representation of x2 followed by an additional digit at the last position therefore we can find the number of set bits in x by finding the number of set bits in x2 and determining whether the last digit in x is 0 or 1 res 0 n1 for i in range1 n1 resi resi2 i 1 return sumres extension find the sum of number of set bits in all the numbers in the range m n answer in countbitsm n return sumres sumres m question find the sum of number of set bits in all the numbers in the range 1 n consider a number x and half of the number x 2 the binary representation of x has all the digits as the binary representation of x 2 followed by an additional digit at the last position therefore we can find the number of set bits in x by finding the number of set bits in x 2 and determining whether the last digit in x is 0 or 1 extension find the sum of number of set bits in all the numbers in the range m n answer in countbits m n return sum res sum res m
def countBits(n):
    
    

    res = [0] * (n+1)
    for i in range(1, n+1):
        res[i] = res[i//2] + (i & 1)
    return sum(res)