Python으로 정수의 세트 비트(Set Bit) 개수 세는 방법

이 글에서는 정수의 이진수 표현에서 1로 설정된 비트, 즉 세트 비트(set bit)의 개수를 세는 Python 프로그램을 다양한 방법으로 구현해 보겠습니다.

문제 정의

정수 n이 주어졌을 때, 해당 숫자를 이진수로 변환했을 때 나타나는 1의 개수를 구하는 것이 목표입니다.

예를 들어, n = 15인 경우 이진수 표현은 1111이므로 세트 비트의 개수는 4가 됩니다.

방법 1: 반복문을 사용한 기본 접근법

가장 직관적인 방법은 숫자를 오른쪽으로 한 비트씩 시프트하면서 마지막 비트가 1인지 확인하는 것입니다.

# 비트 개수 세기
def count(n):
    count = 0
    while (n):
        count += n & 1   # 마지막 비트가 1이면 카운트 증가
        n >>= 1          # 오른쪽으로 1비트 시프트
    return count

# 메인
n = 15
print("세트 비트의 개수 :", count(n))

출력 결과

세트 비트의 개수 : 4

동작 원리:

n & 1 연산은 숫자의 가장 오른쪽 비트가 1인지 검사합니다.
n >>= 1 연산은 숫자를 오른쪽으로 한 자리 밀어 다음 비트를 검사 대상으로 만듭니다.
n이 0이 되면 모든 비트를 검사한 것이므로 반복이 종료됩니다.

이 방법의 시간 복잡도는 O(log n)입니다. 비트 수만큼 반복하기 때문입니다.

방법 2: 재귀를 사용한 접근법

같은 로직을 재귀 함수로도 구현할 수 있습니다. 재귀 호출마다 마지막 비트를 더하고 나머지 부분에 대해 다시 호출하는 방식입니다.

# 재귀적 방법
def count(n):
    # 기저 사례(base case)
    if (n == 0):
        return 0
    else:
        # 마지막 비트가 세트되어 있는지 확인 후 재귀 호출
        return (n & 1) + count(n >> 1)

# 메인
n = 15
print("세트 비트의 개수 :", count(n))

출력 결과

세트 비트의 개수 : 4

동작 원리:

n이 0이면 더 이상 세트 비트가 없으므로 0을 반환합니다(기저 사례).
그렇지 않으면 현재 마지막 비트 값(n & 1)에 나머지 비트에 대한 재귀 결과(count(n >> 1))를 더해 반환합니다.

재귀 방식은 코드가 간결하지만, 호출 스택을 사용하므로 매우 큰 수를 다룰 때는 반복문 방식이 더 안전할 수 있습니다.

보너스: 내장 함수 bin() 활용하기

Python에서는 내장 함수를 활용해 한 줄로도 해결할 수 있습니다.

n = 15
result = bin(n).count('1')
print("세트 비트의 개수 :", result)  # 출력: 4

bin(n)은 정수를 '0b1111' 형태의 이진수 문자열로 변환하며, 여기서 '1'의 개수를 세면 됩니다. 실무에서는 이 방법이 가장 간단하고 가독성이 좋습니다.

마무리

이번 글에서는 Python을 사용해 정수의 세트 비트 개수를 세는 세 가지 방법, 즉 반복문 기반 접근법, 재귀 접근법, 그리고 내장 함수 활용법을 살펴보았습니다. 비트 연산(&, >>)의 동작 원리를 이해하면 알고리즘 문제 해결과 성능 최적화에 큰 도움이 됩니다.