[Leetcode 아주 상세한 문제풀이] 191. Number of 1 Bits - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 191번 문제 Number of 1 Bits 다.

우선 문제를 살펴보자.

 

리트코드 191번 문제 Number of 1 Bits 링크

Number of 1 Bits - LeetCode

Number of 1 Bits - LeetCode

 

 

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.
 

Example 1:
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:
Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
 
Constraints:
The input must be a binary string of length 32.

 

 

문제 설명

문제를 간략히 살펴보자. 2진법으로 표현되는 부호가 없는 (unsigned) 정수가 주어지는데, 이때 '1' bits로 표현되는 개수가 몇개인지 찾아내는 문제다. 예를 들어 2진법으로 표현되는 정수가 10011으로 주어져 있다면 '1' bits 로 표현되는 개수가 3개 이기 때문에 3을 리턴하면 된다. 여기서 부호가 없다는 뜻은 +/-으로 표현되지 않는다는 뜻이다. 문제가 간단하기 때문에 곧바로 문제를 풀어보도록 하자.

* 참고로 문제에서 언급된 Hamming weight에 대해 잠시 알아보도록 하자.

"Hamming weight"라는 용어는 이진 시퀀스 내의 0이 아닌 비어 있지 않은 비트의 수를 나타낸다. 다시 말해, 숫자의 이진 표현에서 '1' 비트(또는 설정된 비트)의 개수다. 이 개념은 미국의 수학자이자 컴퓨터 과학자인 리처드 해밍(Richard Hamming)의 이름을 딴 것으로, 오류 감지와 오류 수정 코드에 중요한 기여를 한 컴퓨터 과학자이다.

Hamming weight는 컴퓨터 과학, 정보 이론, 암호학, 디지털 신호 처리와 같은 다양한 분야에서 사용됩니다. 특히 이진 데이터와 이진 수에 대한 연산을 다룰 때 관련이 있습니다. 예를 들어 컴퓨터 과학에서는 이진 숫자의 Hamming weight를 사용하여 알고리즘의 효율성을 판단하고 복잡성을 분석하며 비트 수준 표현에서의 작업을 최적화하는 데 활용될 수 있습니다.

 

 

문제 접근법

이 문제를 풀기 위해서는 파이썬에서 제공하는 bitwise operation에 대한 간단한 이해가 필요하다.

우선 '&' 연산자에 대해 알아보도록 하자.

파이썬에서 & 연산자는 bitwise AND operation으로 다음과 같은 관계를 같는다.

 

즉 A와 B 모두 비트값으로 1을 가질 때만 1을 출력한다.

따라서 이 연산자를 문제에 적용한다면, 해당 입력값과 1을 비교한다면 (입력값 & 1)

해당 입력값 중 1 비트값만 연산을 통해 1을 출력하기 때문에 해당 입력값 중 1 비트값이 몇개인지 알 수 있다.

추가적으로 파이썬에서 제공하는 '>>'연산자에 대해 알아보자.

>> 연산자는 bitwise operation에서 binary 값을 오른쪽으로 옮기는 연산자다.

 

위 예시에서 보는 것처럼 A가 10011의 2진값을 갖는다고 생각해보자.

이때 >>1 operation은 A를 한 칸 오른쪽으로 옮기고 >>2 operation는 두 칸을 옮긴다.

따라서 이 연산자를 문제에 적용한다면 주어진 값의 맨 오른쪽 값1과 비교 후

이 연산자를 이용해 전체 값을 오른쪽으로 한 칸 옮기고 다음 연산을 수행하면 된다.

 

 

문제 풀이

코드로 한 번 살펴보자.

우선 2진값을 입력받을 함수를 정의해 준다 (line 1)

그리고 주어진 2진값에서 1의 개수가 몇개인지 count 해줄 변수를 하나 설정해 준다 (line 2)

그리고 while loop를 돌리는데 (line 3)

이때 앞서 설명한 연산자 &를 이용해 입력된 값 n과 1을 bitwise AND로 연산해준다.

이때 주어진 값 중 가장 오른쪽에 위치한 값(=least significant value) 만 연산된다는 점을 참고하자. (연산자 성질에 따라)

그리고 이 값을 count에 넣어준다.

우리가 찾고자 하는 것은 입력된 값에 존재하는 1 bit의 개수이기 때문에 이 연산의 결과를 그대로 추가해주면 된다.

& 연산 후 앞서 설명한대로 >> 연산자를 이용하여 입력된 값을 오른쪽으로 한 칸 옮겨준다 (line 5)

여기서 옮기는 것은 bitwise operation임을 다시 한 번 더 명심하자.

while loop를 나오면 count값을 리턴해준다 (line 6)

 

 

문제 풀이 코드

def hammingWeight(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count
 
# Test cases
n1 = 0b00000000000000000000000000001011
print(hammingWeight(n1))  # Output: 3
 
n2 = 0b00000000000000000000000010000000
print(hammingWeight(n2))  # Output: 1
 
n3 = 0b11111111111111111111111111111101
print(hammingWeight(n3))  # Output: 31