파이썬으로 숫자의 이진수 표현에서 1인 비트 개수 구하기

숫자 n이 주어졌을 때, 그 숫자를 이진수(binary)로 표현했을 때 포함된 1의 비트 개수를 구하는 문제입니다.

예를 들어 입력값이 12라면, 12의 이진수 표현은 1100이므로 출력 결과는 2가 됩니다.

문제 해결 접근 방법

이 문제는 비트 연산을 활용하면 간단하게 해결할 수 있습니다. 다음 단계를 따릅니다:

• 카운트 변수를 0으로 초기화합니다.
• n이 0이 아닌 동안 반복합니다:
  • 현재 n과 1을 비트 AND(&) 연산하여 가장 오른쪽 비트가 1인지 확인하고, 그 결과를 카운트에 더합니다.
  • n을 오른쪽으로 한 비트 시프트(즉, 2로 나눈 몫)하여 다음 비트를 검사 대상으로 만듭니다.
• 반복이 끝나면 카운트 값을 반환합니다.

구현 예제

아래 파이썬 코드로 위 로직을 구현해 보겠습니다.

class Solution:
    def solve(self, n):
        count = 0
        while (n):
            count += n & 1
            n >>= 1
        return count

ob = Solution()
print(ob.solve(12))

입력

12

출력

2

동작 원리 설명

코드가 어떻게 동작하는지 단계별로 살펴보겠습니다.

• n & 1: 숫자와 1을 비트 AND 연산하면 가장 오른쪽 비트(LSB)만 남게 됩니다. 이 값이 1이면 해당 자리의 비트가 1이라는 뜻입니다.
• n >>= 1: 오른쪽 시프트 연산은 n을 2로 나누고 소수점 이하를 버리는 것과 같습니다. 이렇게 하면 이미 확인한 비트가 제거되어 다음 비트를 검사할 수 있습니다.
• n이 0이 되면 모든 비트를 확인한 것이므로 반복을 종료합니다.

12의 경우를 예로 들면: 1100 → 첫 번째 비트 0 → 두 번째 비트 0 → 세 번째 비트 1 → 네 번째 비트 1 → 총 2개의 1비트가 발견됩니다.

시간 복잡도

이 알고리즘은 n의 이진수 자릿수만큼 반복하므로 시간 복잡도는 O(log n)입니다. 추가로, 파이썬에서는 내장 함수 bin(n).count('1') 또는 Python 3.10 이상에서는 n.bit_count()를 사용하여 같은 결과를 더 간단히 얻을 수도 있습니다.