Python으로 1부터 n까지 모든 숫자의 세트 비트(Set Bit) 총 개수 구하기

양의 정수 n이 주어졌을 때, 1부터 n까지의 모든 숫자를 이진수(binary)로 변환한 뒤 각 숫자에 포함된 세트 비트(set bit, 값이 1인 비트)의 총 개수를 계산하는 문제입니다.

예시

입력 : n=3
출력 : 4

n=3인 경우 각 숫자의 이진 표현과 세트 비트 개수는 다음과 같습니다.

• 1 → 001 (세트 비트 1개)
• 2 → 010 (세트 비트 1개)
• 3 → 011 (세트 비트 2개)

따라서 전체 세트 비트의 합은 1 + 1 + 2 = 4가 됩니다.

알고리즘

1단계: 양의 정수를 입력받는다.
2단계: 입력받은 숫자를 이진수 형태로 변환한다.
3단계: 합계를 저장할 변수 s를 0으로 초기화한다.
4단계: 1부터 n까지 모든 숫자를 순회하며 세트 비트 개수를 더한다.
5단계: 최종 합계를 출력한다.

예제 코드

# Python program to count set bits
# in all numbers from 1 to n.
def countbits(n):
    # 카운터 초기화
    c = 0
    for i in range(1, n + 1):
        c += bitsetcount(i)
    return c

def bitsetcount(x):
    if (x <= 0):
        return 0
    return (0 if int(x % 2) == 0 else 1) + bitsetcount(int(x / 2))

# Driver program
n = int(input("Enter the value of n"))
print("Total set bit count is", countbits(n))

실행 결과

Enter the value of n10
Total set bit count is 17

코드 설명

bitsetcount() 함수는 재귀(recursion) 방식으로 동작합니다. 입력값 x를 2로 나눈 나머지를 확인해 마지막 비트가 1인지 판별하고, 몫을 대상으로 자기 자신을 다시 호출하며 모든 비트를 검사합니다. x가 0 이하가 되면 재귀를 종료하고 0을 반환합니다.

countbits() 함수는 1부터 n까지의 각 숫자에 대해 bitsetcount()를 호출해 반환된 값을 누적하며, 최종적으로 1부터 n까지의 모든 숫자에 포함된 세트 비트의 총합을 반환합니다.

위 실행 결과에서 n=10을 입력하면 1부터 10까지 숫자들의 이진 표현에 포함된 세트 비트의 총 개수인 17이 출력됩니다.