191. Number of 1 Bits

Description

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1:

• Input: n = 11
• Output: 3
• Explanation: The input binary string 1011 has a total of three set bits.

Example 2:

• Input: n = 128
• Output: 1
• Explanation: The input binary string 10000000 has a total of one set bit.

Example 3:

• Input: n = 2147483645
• Output: 30
• Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

• 1 <= n <= 2³¹ - 1

Follow up: If this function is called many times, how would you optimize it?

Submitted Code

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        set_count = 0             # 1의 갯수 카운트
        while n:                  # n이 0이 되기 전까지 반복
            if (n & 1) == 1:        # n의 맨 오른쪽 비트가 1일 때만 n & 1이 1이 됨
                set_count += 1
            n = n >> 1              # n을 한 비트씩 오른쪽으로 이동

        return set_count

Runtime: 0 ms | Beats 100.00%
Memory: 12.47 MB | Beats 51.34%

>>와 & 연산자를 활용했다.

class Solution(object):
    def hammingWeight(self, n):
        binary_str = bin(n)[2:]
        return binary_str.count("1")

비트를 str 타입으로 변환하는 방법도 사용 가능하다.

Other Solutions

1st

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

time complexity: 𝑂(𝑘) ← n의 비트 수
space complexity: 𝑂(1)

n & 1의 결과를 바로 count에 더하면 0이 나와도 영향이 없기 때문에 if 조건 없이 코드를 단축할 수 있다.

2nd

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

Brian Kernighan 알고리즘을 이용한 방법으로, 비트에서 가장 오른쪽의 1을 하나씩 제거한다. 1의 개수만큼만 반복하기 때문에 전체 비트 수만큼 반복하는 것보다 시간을 더 단축할 수 있다.

💡 Brian Kernighan 알고리즘 원리

• n에서 1을 뺀 값 n - 1은 n에서 가장 오른쪽의 1을 0으로 만들고, 그 오른쪽의 모든 비트는 1로 변경됨
• n & (n - 1) 은 가장 오른쪽 1을 0으로 만들고, 나머지 비트를 그대로 유지함 → 1이 하나 사라지는 효과