LeetCode > 338. Counting Bits

문제 링크 : https://leetcode.com/problems/counting-bits/

주어진 n까지의 범위에서 이진수로 바꾸었을 떄 1의 개수들을 반환하는 문제이다..

처음에 일일이 환산한 뒤 result에 append 할까 생각했다가

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?

을 읽고 다른 방법을 구글링해보았는데
비트 연산자 & 를 이용한 풀이를 알게 되었다

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [0]
        for i in range(1,n+1):
            res.append(res[i&i-1]+1)
        return res

사실 res[i&i-1]+1의 식이 나오게 된 로직이 잘 이해가 가지 않는다..
일단 & 연산자가 둘 다 1이면 1을 반환하게 하는 연산자니까.. 일일이 이진수에서 count하는 방식이 아닌 1만 카운트하는 방식이지 않을까.. 정도로 이해함

어렵다

Runtime: 84 ms, faster than 89.97% of Python3 online submissions for Counting Bits.
Memory Usage: 20.9 MB, less than 32.49% of Python3 online submissions for Counting Bits.

+)비트연산자 &
& : 비트 연산자 (Bitwise)
다음 예제는 7과 2를 &로 비트 연산합니다. 비트 연산 후, 2로 계산되는 과정은 주석으로 자세히 설명하였습니다.

result = 7 & 2

print(result)

    7 = 0000 0111
    &  2 = 0000 0010
----------------------
result, 2 = 0000 0010  

Output:

2