포스트

[leetcode] Counting Bits 비트연산

게시
By SouthGlory
3 분읽는 시간
  • 0 5
  • 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?
  • Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def countBits(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        
        dp = [0] * (n+1)

        for i in range(1, n+1):
            # i를 2로 나눈 몫의 1비트 개수 + i가 홀수면 1 추가
            dp[i] = dp[i >> 1] + (i & 1)

        return dp

i » 1 오른쪽 쉬프트

1
2
3
4
5
6
7
8
9
10
11
12
13

i >> 1  # i를 2로 나눈 몫 (소수점 버림)

# 예시:
5 >> 1  # 5 // 2 = 2
4 >> 1  # 4 // 2 = 2  
3 >> 1  # 3 // 2 = 1
```

**비트 관점에서:**
```
5 = 101 (이진수)
5 >> 1 = 10 (이진수) = 2 (십진수)
# 맨 오른쪽 비트가 사라짐

i & 1 (AND 연산)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

i & 1  # i가 홀수면 1, 짝수면 0

# 예시:
5 & 1  # 1 (홀수)
4 & 1  # 0 (짝수)
3 & 1  # 1 (홀수)
```

**비트 관점에서:**
```
5 = 101
1 = 001
---------
5 & 1 = 001 = 1  # 마지막 비트가 1이면 홀수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# n = 5일 때 단계별 계산
dp = [0, 0, 0, 0, 0, 0]  # 초기화

# i = 1: 1 = 1 (이진수)
dp[1] = dp[1 >> 1] + (1 & 1)
      = dp[0] + 1
      = 0 + 1 = 1

# i = 2: 2 = 10 (이진수)  
dp[2] = dp[2 >> 1] + (2 & 1)
      = dp[1] + 0
      = 1 + 0 = 1

# i = 3: 3 = 11 (이진수)
dp[3] = dp[3 >> 1] + (3 & 1) 
      = dp[1] + 1
      = 1 + 1 = 2

# i = 4: 4 = 100 (이진수)
dp[4] = dp[4 >> 1] + (4 & 1)
      = dp[2] + 0  
      = 1 + 0 = 1

# i = 5: 5 = 101 (이진수)
dp[5] = dp[5 >> 1] + (5 & 1)
      = dp[2] + 1
      = 1 + 1 = 2
```

### 5. 왜 이게 작동하나?
```
숫자 5 = 101 (이진수)
       ↓
   10 (오른쪽으로 1비트 시프트) = 2
   + 1 (마지막 비트가 1이었으므로)
   = dp[2] + 1 = 1 + 1 = 2

#leetcode #CountingBits #shift #and #쉬프트연산 #AND연산

개발, CS기초
CS LeetCode 알고리즘
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.