Sum of ones

n = int(input())

def f(m):
    if m == 0:
        return 0
    if m == 1:
        return 1
    if m % 2 == 0:
        return f(m-1) + str(bin(m)).count("1")
    k = m // 2
    return 2*f(k) + k+1


def g(k):
    return sum([str(bin(m)).count("1") for m in range(k+1)])


# print({k: f(k)-g(k) for k in range(1, 20)})

print(f(n))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED