[알고리즘 설명][C++, Python] 비트마스킹(bit mask)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : 비트마스킹은 말 그대로 0과 1로 이루어진 비트(bit) 단위로 연산하는 알고리즘이며, and, or, xor, not 연산으로 이루어져 있습니다.

 

EE 분야 전공자라면 알겠지만 디지털 논리 회로에서 논리게이트 종류로 AND, OR, NOT, XOR 아시죠?

CS 분야에서는 비트마스킹으로 여러 개의 비트들을 한꺼번에 연산합니다.

 

그래도 여기 비전공자들이 있을 수 있으니 and, or, not, xor 연산을 초간단하게 알려드리겠습니다.

[AND 연산]

Y = A & B

A와 B가 모두 1이어야 출력 Y도 1이고 둘 중 하나라도 0이면 출력 Y가 0입니다.

A	B	Y
0	0	0
0	1	0
1	0	0
1	1	1

[OR 연산]

Y = A | B

A와 B 중 하나라도 1이면 출력 Y는 1이 되고 A와 B 모두 0이어야 출력 Y가 0입니다.

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	1

[NOT 연산]

Y = ~A

A가 0이면 Y는 1, A가 1이면 Y는 0이 됩니다.

A	Y
0	1
1	0

[XOR 연산]

Y = A ^ B

A와 B가 서로 같으면 출력 Y가 0, A와 B가 서로 다르면 출력 Y가 1이 됩니다.

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

 

그러면 본격적으로 비트마스킹에 설명을 하자면 비트마스킹은 "여러 개의 비트를 한꺼번에 연산하는 알고리즘"입니다.

A = 1100이고 B = 1010일 때 A * B, A | B, ~A, ~B, A ^ B 연산 과정 및 결과를 표로 간단하게 알아보록 하겠습니다.

[A & B]

A	1	1	0	0
B	1	0	1	0
A * B	1	0	0	0

[A | B]

A	1	1	0	0
B	1	0	1	0
A | B	1	1	1	0

[~A]

A	1	1	0	0
~A	0	0	1	1

[~B]

B	1	0	1	0
~B	0	1	0	1

[A ^ B]

A	1	1	0	0
B	1	0	1	0
A ^ B	0	1	1	0

 

이게 바로 비트마스킹입니다.

정말 쉽죠?

2진수와 10진수는 전공자라면 당연히 알고 있겠지만 비전공자는 모를 수도 있으니 여기서 초간단하게 2진수와 10진수 변환 과정을 초간단하게 설명하고 넘어갑니다.

[2진수 -> 10진수]

1100(2진수) -> 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 = 12(10진수)

[2진수 -> 10진수]

12(10진수)

-> 12 / 2 = 몫 6 ... 나머지 0

-> 6 / 2 = 몫 3 ... 나머지 0

-> 3 / 2 = 몫 1 ... 나머지 1

-> 1 / 2 = 몫 0 ... 나머지 1

나머지들을 역순으로 배치하면 1100(2진수)가 됩니다.

 

그러므로 A=0b1100, B=0b1010일 때 이것을 C++ 소스 코드로 구현해보겠습니다.

#include <iostream>

using namespace std;

int main() {
    int A, B;
    A = 12; // 이진수 : 1100
    B = 10; // 이진수 : 1010

    cout << (A & B) << '\n'; // AND
    cout << (A | B) << '\n'; // OR
    cout << (~A) << '\n';    // NOT (부호 있는 정수라 보수 표현으로 출력됨)
    cout << (~B) << '\n';    // NOT
    cout << (A ^ B) << '\n'; // XOR
    return 0;
}

 

출력 결과
8
14
-13
-11
6

아까 위에서 &, |, ~. ^ 연산한 결과를 10진수로 출력하게 됩니다.

A & B = 1100(12) & 1010(10) = 1000(8)

A | B = 1100(12) | 1010(10) = 1110(14)

~A = ~ 0000 0000 0000 0000 0000 0000 0000 1100(12) = ~ 1111 1111 1111 1111 1111 1111 1111 0011(-13)

~B = ~ 0000 0000 0000 0000 0000 0000 0000 1010(10) =  ~ 1111 1111 1111 1111 1111 1111 1111 0101(-11)

A ^ B = 1100(12) ^ 1010(10) = 0110(6)

 

실제 A와 B는 int 자료형이라서 각각 4바이트(32비트) 정도 할당된 상태이나 &, |, ^ 표현 과정에서 어차피 나머지 28비트는 모두 0이니 편의상 4비트 부분만 표현한 것입니다.

~A, ~B는 실제로 맨 왼쪽 비트가 1인 음수로 표현하게 되는데 EE 분야 및 CS 분야에서는 1의 보수(One's complement)라고 부르지만 비전공자에게는 낯설기만 합니다.

 

그래서 1의 보수 공식은 아래 수식을 따라주기만 하면 됩니다.

$$ \text{1의 보수}(~A) = -(x+1) $$ $$ \text{2의 보수}(-A) = \text{1의 보수}(~A) + 1 $$

예시로 ~A를 10진수로 표현하면 x=12이므로 ~A = -(12+1) = -13이 됩니다.

그러므로 -A를 구할려면 ~A가 -13이니 -A = ~A + 1 = -13 + 1이 되며 이것이 바로 양수를 음수로 변환하는 과정입니다.

 

마찬가지로 -12를 다시 12로 변환할려면 우선 -12를 ~ 연산하면 ~(-12) = -(-12+1) = 11이 되고

-(-12) = ~(-12) + 1 = 11 + 1 = 12가 됩니다.

이것이 바로 컴퓨터가 음수 연산하는 방법입니다.

 

이렇게 해서 오늘 비트마스킹을 초간단하게 알아봤습니다!

전공 서적에서는 비트마스킹이 무슨 엄청 어려운 알고리즘처럼 묘사되어 있으나 결국 컴퓨터가 0과 1로 연산하는 과정을 묘사하는 것 뿐입니다.

 

아 맞다. 아까 C++ 소스 코드를 Python으로 아래와 같이 작성하면 동일한 결과를 얻을 수 있습니다.

A, B = 12, 10

print(A & B)
print(A | B)
print(~A)
print(~B)
print(A ^ B)