비트마스킹 (with 비트 연산자)

Bit란 Binary digit 의 약어입니다. 즉, 이진수라는 뜻입니다.

컴퓨터는 이진수만 이해할 수 있습니다. 그리고 컴퓨터의 값의 최소 단위는 bit입니다. (메모리는 1byte = 8bit입니다.)

따라서 비트 마스킹이란, 이런 bit를 끄거나 켜는 것을 의미합니다. (0: 끔, 1 : 켬)

 

비트마스킹을 배워야하는 이유는 무엇일까요?

비트마스킹은 불리언 배열을 하나의 숫자로 대체할 수 있기 때문입니다.

예를 들어 [1, 0, 1, 0] 이라는 bool 배열이 있다면, 이는 1010(이진수, 10이라는 값)로 나타낼 수 있습니다. 

 

이렇게 이진수로 나타낸 값에 비트 연산자를 적절히 활용하면, 다양한 기능을 쉽고 간편하게 구현할 수 있게 됩니다.

 

 

비트 연산자

& (and)	and 연산자, 두 비트 전부 1이어야 1이 된다.
| (or)	or 연산자, 두 비트 중 하나라도 1이면 1이 된다.
^ (xor)	xor 연산자, 서로 다른 비트일 경우에만 1이 된다.
~   (tilde, weird)	1의 보수 연산자, 모든 비트를 반전한다.
<< (Logical left shift)	비트를 왼쪽으로 한칸씩 민다. (참고- Arithmetic Left Shift도 같다. )
>> (Arithmetic right shift)	비트를 오른쪽으로 한칸씩 밀되, MSB는 기존의 비트로 채운다. (1이면 1로, 0이면 0으로)

참고로 shift는 Logical, Arithmetic 이외에도 Circular 가 존재합니다. (연산자가 존재하지는 않는다. x86 어셈블리 명령어엔 존재한다.)

 

또한 ~ 연산자는 1의 보수 연산자답게 아래와 같은 공식이 성립합니다.

~A + 1 = -A 

~A = -(A+1)

 

보수와 관련된 포스팅은 아래에서 확인해보세요.

https://ocahs.tistory.com/58

진법과 보수

 

 

비트 연산자 대표 로직

비트 연산자는 보통 자주 쓰이는 예시가 있습니다. 

대표적으로 , (1 << n) 이라는 값은 n비트가 켜진 값을 의미합니다. 

 

예를 들어 1 << 3 은 오른쪽에서 3번째 비트가 켜진 것을 의미합니다. (비트는 0번째부터 시작)

즉,  01000 을 의미하며 8을 의미하기도 합니다.

 

다음은 아주 자주 쓰이는 로직-코드 모음입니다. S를 대상이 되는 피연산자라고 가정합니다.

로직	코드
idx번째 비트 끄기	S &= ~(1 << idx)
idx번째 비트 XOR 연산	S ^= (1 << idx)
최하위 켜져있는 비트 찾기	idx = (S & -S), 여기서 -S는 2의 보수를 생각하면 됩니다. (~연산을 한 뒤, +1 한 값)
크기가 n인 집합의 모든 비트를 켜기	(1 << n) - 1
idx번째 비트를 켜기	S |= (1 << idx)
idx번째 비트가 켜져있는지 확인하기	if( S & (1 << idx) )

 

 

비트 연산자 활용 예시 (경우의 수, 매개변수 전달)

이제 실제로 비트마스킹을 활용하는 예시를 살펴봅시다.

경우의 수

#include <bits/stdc++.h>
using namespace std;
const int n = 4;
int main() {
    string arr[n] = {"a","b","c","d"};
    for(int i = 0; i < (1 << n); i++){
        string ret = "";
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                ret += (arr[j] + ", ");
            }
        }
        cout << ret << "\n";
    }
    return 0;
}

 

총 4개의 후보가 있으니, 1 << 4 == 16 직전인 15(1111)까지 반복하며 하나 하나 모든 경우의 수를 출력하면 됩니다.

만약 조합을 사용한다면 4C1, 4C2, 4C3, 4C4 를 모두 고려해야하는데, 비트마스킹을 이용하니까 단 한줄의 반복문으로 가능해지는 것을 볼 수 있습니다. 또한 특정 비트에 해당하는 아이템이 사용할 것인지는 i & (1 << j) 연산을 사용하여 체크할 수 있습니다.

 

매개변수

#include <bits/stdc++.h>
using namespace std;
const int n = 4;
string arr[n] = {"a","b","c","d"};

void go(int num){
    string ret = "";
    for(int i = 0; i < 4; i++){
        if(num & (1 << i)) ret += arr[i] + " ";
    }
    cout << ret << '\n';
    return;
}

int main() {
    for(int i = 0; i < n; i++){
        go(1 | (1 << i));
    }
    return 0;
}

 

이 경우에는 "a" 라는 매개변수가 포함이 되어있고 이후 "a", "a b", "a c", "a d" 와 같이 매개변수를 더해서 넣어주는 방식입니다.

go의 매개변수로 (1 | 1 << i)를 넣어 현재 켜질 비트를 넘겨주는데요, 1을 무조건 넣어줌으로써 "a"는 반드시 들어가게 됩니다.

 

그리고 go 함수 내부에서는 그렇게 넘겨받은 파라미터에 & (1 << i)를 해서 켜진 비트에 해당하는 값을 가져와 ret에 붙여줍니다.

 

 

비트 마스킹의 한계

그러나 이런 비트마스킹도 한계는 물론 있습니다.

int 형이 32bit이므로, 최대 32개의 아이템에 대해서만 비트 마스킹을 진행할 수 있다는 점입니다.

 

물론 long long을 사용하면 64 bit이긴 하지만, 그렇게 많은 경우의 수를 다룰 때는 어차피 1억을 가뿐히 넘겨서(2^64) 시간 초과가 날 가능성이 매우 높습니다. (2^30만 해도 10억이 넘음)

---

긴글 읽어주셔서 감사합니다.