73. Number of 1 Bits

리트코드

• 부호없는 정수형 (Unsigned Integer)을 입력받아 1비트의 개수를 출력하라.

1. 1의 개수 계산 (24ms)

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

• 이 문제의 결과는 모두 0으로 구성된 비트들과의 해밍 거리(Hamming Distance)로 이를 해밍 가중치(Hamming weight)라고 부른다.

  • 참고로 해밍 거리는 두 정수 도는 두 문자열의 차이를 말한다. (여기서는 1의 개수 차이)

• 해밍 거리는 A XOR B였고, 그렇다면 해밍 가중치는 B를 0으로 두면 된다.

  • y의 값을 비트의 전체 길이에 맞춰 00000000000000000000000000000으로 둔다.

  • 0을 32번이나 입력할 필요는 없다. 파이썬이 자동으로 처리해주기 때문에 0 하나만 둬도 충분하다.

  • 또한, B는 0이므로 XOR은 생략이 가능하다.

    그러므로 이진수에서 1의 개수를 헤아리는 정도로 쉽게 풀이할 수 있다.

2. 비트 연산 (24ms)

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            #1을 뺀 값과 AND 연산 횟수 측정
            
            n &= n - 1
            count += 1
        return count
        

• 그렇다면 파이썬의 문자열 기능을 사용하지 않고 비트 연산만으로 1비트의 개수를 헤아릴 수 있을까?

• 이진수의 특징부터 살펴보자.

  • 1000에서 1을 빼면 0111이 된다. 이 두 값을 AND 연산하면 다음과 같다.

    • bin(0b1000 & 0b0111) >>> '0b0'

    • 결과는 0이 된다.

  • 1010에서 1을 빼면 1001이다. 이 두 값을 AND 연산한다.

    • bin(0b1010 & 0b1001) >>> '0b1000'

  • 이처럼 1을 뺀 값과 AND 연산을 할 때마다 비트가 1씩 빠지게 된다.

    • 그렇다면 0이 될 때까지 이 작업을 반복하면 전체 비트에서 1의 개수가 몇 개인지 알 수 있다는 이야기가 된다.
  
  

• 코드에서 n이 0이 될 때까지 반복하고, 그 횟수를 리턴하면 그 값이 바로 1비트의 개수가 된다.