Sum of ones

#!/usr/bin/env python3

import sys
import math
import collections
import itertools

input = sys.stdin.read

# Define input versions
def input_list():
    """Returns a list of integers from a single input line"""
    return list(map(int, input().split()))

def input_int():
    """Returns a single integer from input"""
    return int(input())

def input_str():
    """Returns a single string from input"""
    return input().strip()

def print_output(output):
    """Efficiently prints output"""
    sys.stdout.write(str(output) + "\n")


# Math Util
def is_prime(n):
    """Returns True if n is a prime number, False otherwise"""
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True


# Function to count the number of 1 bits from 1 to n
def count_one_bits(n):
    count = 0
    power_of_2 = 1
    
    # Traverse over each bit position
    while power_of_2 <= n:
        # Count full cycles of '0's and '1's in current bit position
        full_cycles = (n + 1) // (power_of_2 * 2)
        remainder = (n + 1) % (power_of_2 * 2)
        
        # Add number of '1's from full cycles
        count += full_cycles * power_of_2
        
        # Add '1's from the remainder part
        if remainder > power_of_2:
            count += remainder - power_of_2
        
        # Move to the next bit position
        power_of_2 *= 2
    
    return count

def main():
    # Input
    n = int(input().strip())

    # Output the total number of 1 bits from 1 to n
    print(count_one_bits(n))

if __name__ == "__main__":
    main()

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