[Top Interview Questions] 191. Number of 1 Bits

정답)

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0

        for _ in range(32):
            if n & 1 == 1:
                res += 1
            
            n >>= 1
        
        return res

문제)

문제출처

 

2진수로 표현된 정수를 받아 그 2진수에서 1이 몇 개 있는지 리턴하는 함수를 만드시오.

 

예시 1)

n = 00000000000000000000000000001011

output = 3

 

예시 2)

n = 00000000000000000000000010000000

output = 1

 

예시 3)

n = 11111111111111111111111111111101

output = 31

 

제한)

인풋의 길이는 32입니다.

풀이)

저번 문제와 비슷하게 &연산자와 >>연산자를 이용하는 문제입니다.

 

n의 맨 끝자리가 1이면 카운트하는 변수에 1을 더해주고

>>연산자를 이용해 다음 끝자리를 확인하는 방식입니다.

 

제한에서 인풋의 길이가 32라고 했기 때문에 이 과정을 32번 반복해 줍니다.

 

def hammingWeight(self, n: int) -> int:
        res 변수

        32번동안:
            n의 끝자리가 1이면:
                res에 1을 더함
            
            n의 끝자리를 업데이트
        
        res를 리턴

n의 끝자리를 확인)

1이 몇 개인지 저장해 줄 변수 res에 0을 저장해 줍니다.

 

그리고 인풋의 길이인 32번 동안 n의 끝자리 숫자를 확인해 줍니다.

 

저번 문제와 비슷하게 n & 1을 하게 되면 n의 끝자리 숫자를 그대로 알 수 있습니다. 

10001 & 1을 하게 될 때 1이 나오는 것처럼 말이죠.

 

10001 & 1

그래서 만약 n & 1 == 1 이라면 res에 1을 더해 현재까지 n에 1이 몇 개 존재하는지 저장해 줍니다.

 

def hammingWeight(self, n: int) -> int:
        res = 0

        for _ in range(32):
            if n & 1 == 1:
                res += 1

n의 끝자리를 업데이트)

위의 과정에서 n의 끝자리가 1인지 확인했다면 이제 다음 끝자리를 확인해야 됩니다.

 

만약 n의 비트가 10001 이라면

아까 과정에서 1을 확인했으니 다음에는 바로 옆의 0을 확인해 줘야겠죠?

 

그래서 저번에 사용한 >> 연산자를 이용해 옆의 숫자들을 오른쪽으로 한 칸 당겨주겠습니다.

10001    =>    01000

 

10001 >> 1

옆에 있던 0이 오른쪽으로 이동했습니다.

이렇게 되면 다음 루프 때 이동한 0이 1인지 확인하는 절차를 거치게 됩니다.

 

그렇게 32번 루프를 돌리고 나면 마지막으로 1이 몇 개인지 저장하던 변수 res를 리턴합니다.

 

def hammingWeight(self, n: int) -> int:
        res = 0

        for _ in range(32):
            if n & 1 == 1:
                res += 1
            
            n >>= 1
        
        return res

 

 

이번 문제는 이때까지 나온 비트 연산 문제들 중에 가장 쉽고 직관적이지 않나 싶습니다. 이 문제가 가장 먼저 나왔으면 어땠을까 하는 아쉬움이 있네요. 

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)