이진수?
2진법은 0과 1이라는 두 개의 숫자만을 사용하여 수를 나타내는 진법
비트마스킹 알고리즘을 공부하기 우선 이진수부터 제대로 알아보자!!
이진수는 두 개의 숫자만을 사용하여 수를 나타낸 기법입니다.
10을 이진수로 나타내면 ?? = 1010
엥? 어떻게 10 -> 1010이 되었을까요?
10진수 -> 2진수
숫자 10 -> 1010이 되는 과정을 알아보겠습니다.
이진수는 두 개의 숫자만을 사용하는데 1, 0이 사용됩니다.
그럼 왜 2진수일까? 닉값하는 이유가 있습니다.
1010 -> (1 x 2³ ) + (0 x 2² ) + ( 1 x 2¹ ) + (0 x 2⁰) 과정으로 인해 10이 됩니다.
2진수의 덧셈
1011 (10진수로 11)
+ 1101 (10진수로 13)
--------
11000 (10진수로 24) 10진수는 자릿수가 0~9지만, 2진수는 자릿수가 0과 1 뿐입니다.
그래서 1 + 1은 2가 아니라 다음 자리로 올림(Carry) 이 발생하게 됩니다.
2진수 뺄셈
1011 (10진수로 11)
- 0110 (10진수로 6)
--------
0101 (10진수로 5)이진수에서 0 - 1은 계산이 안 되기 때문에 윗자리에서 빌려와야 합니다.
& 연산자
| 연산 | 결과 |
|---|---|
| 0 & 0 | 0 |
| 0 & 1 | 0 |
| 1 & 0 | 0 |
| 1 & 1 | 1 |
1 & 1 즉 true true일 때만 1이나오고 그 외는 다 0이 나옵니다.
ex ) 1001 &1011 = 1001
| 연산자
| 연산 | 결과 |
|---|---|
| 0 & 0 | 0 |
| 0 & 1 | 1 |
| 1 & 1 | 1 |
| 1 & 1 | 1 |
하나라도 1이라면 1이 나옵니다
ex ) 1001 | 1000 = 1001
<<연산자(왼쪽 시프트 연산자)
a << b
a = 시프트할 값
b = 시프트할 비트의 수
5 << 1 // 비트를 왼쪽으로 1칸 이동
Before: 00000101 (5)
Shift : 00001010 (10)즉 5 << 1 = 5 * 2¹ 이 됩니다.
5 << 3은 어덯게 될가요?
5 * 2³ = 40 이 됩니다.
x << n = x * 2ⁿ
>>연산자(오른쪽 시프트 연산자)
<<와 반대겠죠? 바로 나눗셈 입니다.
5 >> 1
Before: 00000101 (5)
Shift : 00000010 (2)a >> b 바로 예시로 볼가요?
5 >> 1을 수식으로 표현해 보겠습니다.
x >> n = x / 2ⁿ
XOR ^ 연산자
| A | B | A^B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
true ^ true = false
false ^ false = false
나머지는 true 입니다.
즉, 짝이 안맞는 놈들만 1이 나오게 됩니다.
NOT ~ 연산자
각 비트를 반전하는 연산
즉, 0 → 1, 1 → 0
여기서 눈여겨 봐야할건
-value = ~value + 1이라는 것입니다.
바로 예시를 보겠습니다.
-16 = ~16 + 1 입니다.
-16을 2진수로 나타내면 1111111111110000입니다 이제 이를 +16으로 나타내보겠습니다.
우선 비트를 반전시킵니다.
0000000000001111 // 반전 시킨 수
여기에 + 1을 더하면 어떻게 될가요?
0000000000010000 // = 16-value = ~value + 1 또는 ~value = -(value + 1)
