Number of 1 Bits

문제 링크

• https://leetcode.com/problems/number-of-1-bits/

문제 설명

양의 정수 n이 주어지면 이진 표현에서 설정된 비트 수를 반환하는 함수(해밍 가중치라고도 함)를 작성합니다.

• 입력: 정수 n
• 출력: n의 이진 표현에서 1로 설정된 비트의 개수

예제

• 예제 1
  • 입력: n = 11
  • 출력: 3
  • 설명: 11의 이진 표현은 1011이며, 총 3개의 1이 있습니다.
• 예제 2
  • 입력: n = 128
  • 출력: 1
  • 설명: 128의 이진 표현은 10000000이며, 1이 1개 있습니다.
• 예제 3
  • 입력: n = 2147483645
  • 출력: 30
  • 설명: 2147483645의 이진 표현은 1111111111111111111111111111101이며, 총 30개의 1이 있습니다.

풀이 전략

이 문제를 풀기 위해 몇 가지 접근 방법이 있습니다.

1. 비트 연산자 활용:
   • n을 오른쪽으로 1비트씩 쉬프트하면서, 매번 n & 1을 통해 마지막 비트가 1인지 확인합니다. 이때 n & 1이 1이면 set bit이므로 카운트를 증가시키고, n을 계속 오른쪽으로 쉬프트하여 0이 될 때까지 반복합니다.
2. Brian Kernighan’s Algorithm:
   • n에서 가장 오른쪽에 있는 1 비트를 0으로 만들면서, set bit의 개수를 카운트합니다. n = n & (n - 1)을 반복하여 이 작업을 수행할 수 있으며, 매 연산이 하나의 1을 제거하므로 시간 복잡도는 set bit 개수만큼입니다.
3. Python의 bin() 함수 사용:
   • 파이썬의 bin() 함수를 사용하여 n의 이진 표현을 문자열로 변환한 뒤, 문자열 내 1의 개수를 세는 방법도 가능합니다. 이 방식은 코드가 간결하지만, 비트 연산을 사용하지 않기 때문에 속도 면에서 비효율적일 수 있습니다.

코드 분석

방법 1: Brian Kernighan’s Algorithm

이 알고리즘은 가장 효율적인 방법으로, set bit의 개수만큼 연산을 수행합니다.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= (n - 1)  # 가장 오른쪽의 1 비트를 제거
            count += 1    # 제거할 때마다 count 증가
        return count

• 동작 원리:
  • n & (n - 1)은 n의 가장 오른쪽에 있는 1을 제거하는 연산입니다.
  • 예를 들어, n = 1011(10진수 11)일 때, n - 1은 1010이 되고 1011 & 1010은 1010이 되어 가장 오른쪽의 1이 제거됩니다.
  • 이 작업을 반복하여 n이 0이 될 때까지 진행하고, 제거된 set bit의 개수를 count에 누적합니다.
• 시간 복잡도: O(k), 여기서 k는 n의 set bit 개수입니다. 따라서 n의 크기에 따라 비트 연산 횟수가 달라집니다.

방법 2: 비트 쉬프트 연산을 이용한 방법

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1  # 마지막 비트가 1이면 count 증가
            n >>= 1         # 오른쪽으로 1비트 쉬프트
        return count

• 동작 원리:
  • n & 1 연산을 통해 n의 마지막 비트가 1인지 확인합니다. 1이면 count를 증가시킵니다.
  • n을 오른쪽으로 1비트씩 쉬프트하여 마지막 비트가 점점 이동하게 하고, n이 0이 될 때까지 반복합니다.
• 시간 복잡도: O(log n), 비트 개수만큼 반복하므로 n의 이진수 표현 길이에 비례합니다.

방법 3: bin() 함수 사용

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')

• 동작 원리:
  • bin(n)을 통해 n을 이진 문자열로 변환한 후, .count('1')로 문자열에서 1의 개수를 세어 반환합니다.
• 장점:
  • 코드가 매우 간결하며 파이썬의 내장 함수를 활용하여 직관적입니다.
• 단점:
  • 비트 연산을 사용한 방법들에 비해 속도가 느릴 수 있습니다.
• 시간 복잡도: 문자열 변환과 count에 대한 복잡도가 포함되므로, 다른 방법들보다 비효율적일 수 있습니다.

요약

• Brian Kernighan’s Algorithm은 가장 효율적이며, 이진수에서 set bit만큼의 반복만 필요합니다.
• 비트 쉬프트 연산을 사용하는 방법도 간단하고, 전체 비트를 순회하는 방식입니다.
• bin() 함수 사용은 코드가 매우 간단하지만, 속도가 느릴 수 있습니다.

이 문제에서 Brian Kernighan’s Algorithm이 가장 효율적이고 추천되는 접근법입니다.