Bit: 191. Number of 1 Bits

191. Number of 1 Bits

 

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n: # n > 0:
            res += n % 2 # res += n&1
            n = n >> 1 # n = n // 2       
        return res

 

https://youtu.be/5Km3utixwZs?si=f7G0eyMnnaO_-VMR

 

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n: # n > 0:
            n &= (n-1) # n = n & (n-1)
            res += 1
        return res

 

이 코드는 주어진 정수 n의 이진수 표현에서 1의 개수(해밍 가중치, Hamming Weight) 를 구하는 방법을 구현한 것입니다.

알고리즘의 핵심은 Brian Kernighan 알고리즘으로,

반복할 때마다

n에서 가장 오른쪽에 있는 1 비트를 제거하는 방식으로 동작합니다.

 

요약

• 목적: 주어진 정수 n의 이진수 표현에서 1의 개수를 계산합니다.
• 핵심 아이디어: n & (n-1) 연산을 통해 매 반복마다 n에서 가장 오른쪽에 있는 1 비트를 제거하고, 제거한 횟수를 세어서 최종적으로 1의 총 개수를 반환합니다.
• 효율성: 이 방법은 n에 있는 1의 개수만큼만 반복하기 때문에, 만약 n이 매우 큰 수이지만 1의 개수가 적다면 효율적으로 동작합니다.

"오른쪽 비트"라는 표현 때문에 혼동이 있을 수 있습니다.

여기서 **"가장 오른쪽에 있는 1 비트"**라는 말은 이진수 표현에서 오른쪽(최하위 자리)에서부터 처음 만나는 1을 의미합니다.

꼭 전체 이진수의 가장 오른쪽(최하위 비트)이 1이라는 뜻이 아니라,

우측에서부터 스캔했을 때 처음 발견되는 1을 의미합니다.

예를 들어, n = 12의 이진수 표현은 1100입니다.

• 이진수 1100을 오른쪽에서부터 살펴보면,
  • 가장 오른쪽 비트(2^0 자리는)는 0입니다.
  • 그 다음 비트(2^1 자리는)도 0입니다.
  • 그 다음 비트(2^2 자리는)는 1입니다.

즉, 오른쪽에서 처음 만나는 1은 2^2(4)를 나타내는 비트입니다. 이 비트를 **가장 오른쪽에 있는 1 비트(최하위의 1)**라고 부르는 것입니다.

Brian Kernighan 알고리즘이 동작하는 원리

1. n-1 연산:
   • n = 12 (1100)에서 n - 1 = 11 (1011)입니다.
   • 12 (1100)에서 가장 오른쪽의 1은 2^2의 자리입니다.
   • n - 1 연산은 이 최하위의 1과 그 오른쪽의 모든 비트를 반전시킵니다.
     • 1100에서 2^2 자리가 1인 위치 이후(오른쪽)는 모두 0이었으므로, n - 1에서 해당 자리 이후는 모두 1로 바뀝니다.
     • 결과적으로 1011이 됩니다.
2. n & (n-1) 연산:
   • 이제 n & (n-1)를 계산하면,
     • 1100 & 1011 = 1000이 됩니다.
   • 이 연산은 최하위의 1을 제거하는 효과가 있습니다.
     • 즉, 1100에서 2^2에 해당하는 1이 0으로 바뀌고, 나머지 비트는 그대로 유지됩니다.
3. 반복:
   • 이렇게 n에서 1 비트를 하나씩 제거하면서, 제거한 횟수를 센 것이 바로 해밍 가중치(1의 개수)가 됩니다.

요약

• **"가장 오른쪽에 있는 1 비트"**란 이진수의 최하위의 1을 의미하며, 이는 꼭 이진수의 가장 오른쪽(최하위 비트)이 1이라는 뜻이 아닙니다.
• n = 12 (1100)의 경우, 오른쪽에서 첫 번째 1은 2^2의 자리입니다.
• Brian Kernighan 알고리즘은 n & (n-1) 연산을 통해 이 최하위 1 비트를 제거하면서 1의 개수를 센다는 점에서 효율적으로 해밍 가중치를 구할 수 있습니다.