popcount.py

def popcount(n):
    c = 0
    while n != 0:
        c += n % 2
        n //= 2
    return c


def popcount_range_naive(n):
    return sum(map(popcount, range(n + 1)))


def popcount_range_dp(n):
    dp = [0, 1]
    for i in range(2, n + 1, 2):
        dp.append(dp[i // 2])
        dp.append(dp[i // 2] + 1)
    return sum(dp[:n + 1])


def popcount_range_constant(n):
    c = 0
    group_size = 2
    while group_size // 2 <= (n + 1):
        ones_in_group = group_size // 2
        number_of_groups, leftover_bits = divmod(n + 1, group_size)
        leftover_ones = leftover_bits - (
            group_size // 2) if leftover_bits > group_size // 2 else 0
        ones_in_bit = number_of_groups * ones_in_group + leftover_ones
        c += ones_in_bit
        group_size *= 2
    return c


def main():
    for n in [7, 1000, 5359836]:
        print(popcount_range_naive(n))
        print(popcount_range_dp(n))
        print(popcount_range_constant(n))


if __name__ == "__main__":
    main()

# 0 : 000
# 1 : 001
# 2 : 010
# 3 : 011
# 4 : 100
# 5 : 101
# 6 : 110
# 7 : 111