비트 계산

문제설명

정수 n이 주어졌을 때, 길이가 n + 1인 배열 ans를 반환하세요. 이 배열에서 각 i (0 <= i <= n)에 대해 ans[i]는 i의 이진수 표현에서 1의 개수입니다.

예시 1:

입력: n = 2
출력: [0,1,1]
설명:
0 --> 0
1 --> 1
2 --> 10

예시 2:

입력: n = 5
출력: [0,1,1,2,1,2]
설명:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

제약:

0 <= n <= 105

문제풀이

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

<내 코드의 흐름>

1. countBits라는 메소드를 정의합니다. 이 메소드는 n이라는 정수를 입력으로 받아들이며, 정수 리스트를 반환합니다. 여기서 n: int는 n이 정수임을 나타내고, -> List[int]는 정수 리스트를 반환함을 나타냅니다.
2. 길이가 n + 1인 리스트 ans를 생성하고, 모든 요소를 0으로 초기화합니다. 예를 들어, n이 5이면 [0, 0, 0, 0, 0, 0]이 됩니다.
3. 1부터 n까지 반복문을 시작합니다. 이 반복문은 각 숫자 i에 대해 이진수에서 1의 개수를 계산합니다.
4. ans[i]를 계산합니다. 이때 i >> 1은 i를 오른쪽으로 1비트 이동시켜 2로 나눈 값을 얻고, i & 1은 i의 마지막 비트를 얻습니다.

• 예를 들어, i가 5 (즉, 101 이진수)일 때:
  i >> 1은 2 (즉, 10 이진수)가 되어 ans[2]의 값을 참조합니다.
  i & 1은 101의 마지막 비트인 1이 되어 1을 더합니다.
  따라서 ans[5]는 ans[2] + 1이 됩니다.

5. ans 리스트를 반환합니다.

• 이 리스트는 0부터 n까지의 각 숫자에 대해 이진수에서 1의 개수를 포함합니다.