아주 중요한 질문이야!
i & -i는 Binary Indexed Tree (BIT) 의 핵심 연산 중 하나고,
이 값이 의미하는 것은
i가 담당하는 구간 크기 (LSB: 가장 낮은 1비트의 값)
즉, i & -i는 i의 이진수에서 가장 오른쪽 1이 나타나는 자리의 값이야.
예를 들어 i=12이면, 이진수 1100에서 가장 오른쪽의 1은 0100 → 4야.
✅ 원리 요약
| 표현 | 설명 |
|---|---|
i | 어떤 정수 (예: 12 = 1100) |
-i | 이진수에서 2의 보수를 취한 값 |
i & -i | i에서 가장 오른쪽 1만 남기고 나머지는 0으로 만드는 연산 |
✅ 실제 예시들로 이해해보자
예제 1: i = 12
i = 12 = 00001100
-i = -12 = 11110100 (2의 보수)
i & -i = 00000100 = 4- 12의 가장 오른쪽 1이 4의 자리에 있다는 뜻이야.
- 즉,
i = 12는 BIT에서 4칸을 담당하는 구간의 루트 노드라는 뜻.
예제 2: i = 10
i = 10 = 00001010
-i = -10 = 11110110
i & -i = 00000010 = 2→ 오른쪽에서 두 번째 비트(2의 자리)가 살아있다 → 2 리턴
예제 3: i = 8
i = 8 = 00001000
-i = -8 = 11111000
i & -i = 00001000 = 8→ 8은 2의 거듭제곱 → 자기 자신이 나옴
🧠 왜 이걸 쓰는가?
BIT[i]는 다음 구간들을 담당하고 있어:
i | i & -i | 의미 |
|---|---|---|
| 1 | 1 | 1개 구간 |
| 2 | 2 | 2개 구간 |
| 3 | 1 | 1개만 |
| 4 | 4 | 4개 구간 |
| 5 | 1 | 1개만 |
| 6 | 2 | 2개 |
| 7 | 1 | 1개 |
| 8 | 8 | 8개 구간 |
→ 그래서 i += i & -i를 하면:
i가 담당하는 구간의 다음 상위 루트 노드로 점프하는 거야.
🎯 정리
| 연산 | 설명 |
|---|---|
i & -i | i의 이진수에서 가장 낮은 자리의 1비트 |
| 이 값의 의미 | BIT에서 i가 담당하는 구간 크기 |
| 쓰임새 | update, query에서 상위 노드 이동을 위해 사용 |
✅ 보너스: 직접 계산법
- 정수
i에 대해,
-i는 "2의 보수" =~i + 1이고, i & -i는 그걸 & 해서 오른쪽 1 하나만 남기는 연산이야.
좋아!
그럼 이제 보수가 뭔지,
특히 -i를 계산할 때 나오는 2의 보수(two's complement) 개념을
완전 기초부터, 디버깅하듯이 하나씩 차근차근 설명해줄게.
✅ 용어 먼저 정리
| 용어 | 의미 |
|---|---|
| 1의 보수 | 비트를 뒤집은 것 (0 → 1, 1 → 0) |
| 2의 보수 | 1의 보수에 +1 한 것 (음수를 이진수로 표현하는 방식) |
-i | 2의 보수 형태로 표현된 음수 |
🧠 왜 보수가 필요할까?
컴퓨터는 음수를 저장할 수 없음
→ 그래서 양수의 이진수로 음수를 흉내내야 함.
그 방식이 바로 2의 보수 방식이야.
✅ 2의 보수 만드는 방법 (3단계)
예: i = 5 → -i = -5 만드는 과정
🔹 Step 1: 5를 이진수로 표현 (8비트 기준)
5 = 00000101🔹 Step 2: 1의 보수 (모든 비트를 뒤집기)
00000101 → 11111010🔹 Step 3: 2의 보수 (1의 보수에 +1)
11111010 + 1 = 11111011즉,
-5 = 11111011✅ 이게 바로 컴퓨터가 내부적으로 저장하는 -5의 이진수 형태
✅ 직접 예제 해보기
예제: i = 12 → -12의 2의 보수는?
-
12 = 00001100 -
1의 보수:
11110011 -
+1 →
11110100 -
결과:
-12 = 11110100 (8비트 기준)
확인: i & -i 해보자
i = 00001100
-i = 11110100
i & -i = 00000100 = 4→ 가장 오른쪽 1비트만 남는 걸 확인할 수 있어!
✅ 전체 정리표
| 정수 | 이진수 | 1의 보수 | +1 → 2의 보수 (-i) |
|---|---|---|---|
| 5 | 00000101 | 11111010 | 11111011 |
| 8 | 00001000 | 11110111 | 11111000 |
| 12 | 00001100 | 11110011 | 11110100 |
🎯 요약
| 개념 | 설명 |
|---|---|
| 1의 보수 | 비트를 뒤집기 (0 ↔ 1) |
| 2의 보수 | 1의 보수 + 1 → 컴퓨터가 음수를 표현하는 방식 |
-i | i의 2의 보수 |
i & -i | i에서 가장 오른쪽 1비트만 남기기 → BIT에서 구간 크기 계산용 |
정말 좋은 질문이야!
바로 이 "이진수에서 +1 연산이 어떻게 동작하는지"
즉,
11110011 + 1 = 11110100
이 부분이 잘 이해되지 않았다는 거지?
그럼 이제, 이진수에 +1을 하는 과정을 십진수처럼 자리올림(carry)까지 포함해서
하나하나 자리별로 디버깅하듯 보여줄게.
✅ 문제 상황
시작:
2의 보수를 구하려고 아래 연산을 하는 중이야
1의 보수: 11110011
+1 +00000001
------------------------
결과: 11110100🧠 어떻게 +1이 되는가?
이진수의 덧셈도 십진수와 똑같이 자리올림이 있음
- 1 + 1 → 0, 올림 1
- 1 + 0 → 1, 올림 없음
- 0 + 1 → 1, 올림 없음
🎯 비트 자리별로 계산해보자 (오른쪽 → 왼쪽)
| 비트 위치 (왼→오) | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| 1의 보수 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| +1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 결과 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
🔍 계산 순서:
- 0번 비트 (맨 오른쪽):
1 + 1 = 0, 올림 1 - 1번 비트:
1 + 0 + 올림(1) = 0, 올림 1 - 2번 비트:
0 + 0 + 1 = 1, 올림 0 - 나머지는 그대로 복사됨
→ 최종 결과: 11110100
✅ 십진수로 검산해보자
11110011= 243 (1의 보수)+1→ 244244의 8비트 이진수는?
→11110100✅ 맞음!
🎯 결론 요약
| 개념 | 설명 |
|---|---|
+1 연산 | 오른쪽에서 1 더하고, 1+1이면 0 만들고 올림 1 |
| 1의 보수 → 2의 보수 | 맨 오른쪽 1을 찾고, 그 오른쪽은 전부 0으로 바뀜, 왼쪽은 그대로 유지됨 |
| 이진수 +1 계산은 | 십진수 덧셈과 동일하게 "자리올림" 있음 |
💡 핵심 기억 포인트
2의 보수 = 1의 보수 + 1
+1 연산은 자리올림이 포함된 덧셈이다
