[Leetcode/파이썬] 191. Number of 1 Bits

Number of 1 Bits

---

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 <= 231 - 1

 

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

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

n이 1/2 씩 줄어들기 때문에 무리없이 통과할 것이라고 생각했다. 실제로 $2^{31} - 1$ 의 숫자를 넣어서 수행해본 결과, 무리 없이 진행되었다. 수가 매우 크기 때문에 $O(log N)$ 정도로 줄여야 할 것이라고 생각했고, 이는 절반으로씩 줄이는 방법이 가장 탁월하다고 생각했다. 비트로 푸는 방법도 있던데, 큰 틀에서 보면 똑같은 풀이구나 라는 생각이 든다.