본문 바로가기

코딩/알고리즘

[초급] 비트마스크

이 글에서는 이진법의 성질을 이용해 문제 풀이를 쉽게 해 주는 기법인 비트마스크(Bitmask)에 대해 배워 보겠습니다.

 

이진법

대부분 아시겠지만, 먼저 이진법에 대해 간단하게 정리해 봅시다.

 

우리가 사용하는 수는 십진법입니다. 십진법은 0에서 9까지의 숫자를 이용해서 어떤 정수라도 표현할 수 있습니다. 컴퓨터는 이진법을 사용하는데, 이진법은 0과 1만으로 모든 수를 표현합니다.

 

십진법 수의 맨 오른쪽 자리는 일(1)의 자리입니다. 그 왼쪽 자리는 10의 자리이고, 한 칸 더 왼쪽으로 가면 $10^2 = 100$의 자리입니다.

 

이진법도 마찬가지입니다. 맨 오른쪽 자리는 1의 자리, 그 왼쪽 자리는 2의 자리이고, 계속 한 칸씩 왼쪽으로 갈수록 4의 자리, 8의 자리와 같이 커집니다.

 

간단한 예시로, 십진법 수를 이진법으로 나타내 봅시다.

13 = 1101 (2)

25 = 10101 (2)

 

이 장에서 다룰 주제는 아니지만, 십진법을 이진법으로 변환하는 코드를 짜는 것도 자주 볼 수 있는 유형입니다.

 

더보기

BOJ 2745. 진법 변환 (B2)

X진법 수를 10진법으로 바꾸는 것은 쉽습니다. 오른쪽 자리부터 가중치를 매겨 준 후, 가중치와 각 자리에 쓰인 숫자를 곱해서 모두 더하면 됩니다. 수학적으로는, $D$진법 수 $a_n a_{n-1} a_{n-2} \cdots a_1 a_0$을 10진법으로 나타낸 값은,

$$\sum _{i=0}^{n} a_i D^i$$

가 됩니다. 이 값을 계산해 주기만 하면 됩니다. 문자로 나타내어진 숫자의 고유값을 구하는 것은 아스키 코드를 이용해 쉽게 처리할 수 있습니다.

 

BOJ 11005. 진법 변환 2 (B1)

 

10진법 수를 X진법으로 바꾸는 것은 주로 재귀 함수를 이용합니다. 수를 0이 될 때까지 X로 나눈 뒤, 그 나머지들을 역순으로 배치하면 쉽게 답을 얻어낼 수 있습니다. 재귀 함수가 아닌, while문을 쓰기도 하지만 재귀 함수가 더 쉽습니다.

 

정수 자료형의 저장

컴퓨터는 정수 자료형을 저장할 때 이진법을 이용합니다. 0/1의 두 가지 상태만 나타내면 되기 때문입니다. 0/1을 나타내는 각각의 상태를 비트라고 합니다. 비트의 개수에 따라 나타낼 수 있는 수의 범위가 좌우됩니다.

 

C에서 가장 많이 쓰이는 정수 자료형인 int는 32개의 비트를 가지고 있습니다. 따라서 $2^{32}$가지 수를 표현할 수 있습니다. 부호가 없는 정수 자료형 unsigned int 역시 마찬가지로 32개의 비트를 가지고 있지만, 두 자료형이 나타내는 수의 범위는 조금 다릅니다.

 

unsigned int는 $0 \le N < 2^{32}$를 만족하는 정수 $N$을 저장하고,

int는 $-2^{31} \le N < 2^{31}$을 만족하는 정수 $N$을 저장합니다.

이렇게 범위가 다른 이유는 unsigned int는 음이 아닌 정수만을 저장하기 때문입니다.

 

그렇다면, 음수의 표현은 어떻게 이루어질까요? int 자료형에서 최상위 비트는 $2^{31}$의 자리가 아닌, 부호를 나타내는 용도로 사용됩니다. 그래서 컴퓨터 과학자들은 초기에 $-x$를 나타낼 때는, $x$의 각 비트를 뒤집은 것을 사용하기로 했습니다. 이것을 1의 보수 표현법이라고 합니다. 그런데, 문제가 생겼습니다.

 

$$0 = 0000 _{(2)}$$

$$-0 = 1111 _{(2)}$$

 

(편의상 4개의 비트만 표기했습니다.) 바로 0을 표기하는 방법이 두 가지가 생긴 것입니다. 컴퓨터 과학자들은 이 문제를 해결하는 방법을 고안해 냈습니다. $-x$를 나타낼 때, $x-1$의 비트를 뒤집은 것을 사용하자고 한 것입니다. 이를 2의 보수 표현법이라고 합니다. 예시를 살펴보면, 

 

$$0 = 0000 _{(2)}$$

$$-1 = 1111 _{(2)}$$

 

와 같이 된 것이죠. 이런 재미있는 성질을 이용한 비트 연산 기법이 매우 많이 존재하는데, 오늘 이 기법들을 다루게 될 것입니다.

 

비트 연산

C에서 제공하는 기본 비트 연산은 아래와 같습니다.

&(AND) |(OR) ^(XOR)

<<(LSHIFT) >>(RSHIFT) ~(NOT)

&= |= ^= <<= >>= (위 연산자들과 대입 연산자를 혼합한 연산자들)

하나하나 살펴봅시다. 제목 옆의 기호는 보통 수식을 쓸 때 사용하는 기호이고, 위의 기호는 C언어에서 사용하는 기호입니다.

 

AND ($\wedge$)

1비트 정수에 대해 AND는 아래와 같이 정의됩니다.

A B A&B
0 0 0
0 1 0
1 0 0
1 1 1

일반적인 정수에 대해 AND는, 각 비트별로 AND 연산을 수행한 값으로 정의됩니다.

 

5 & 3 = 0101 & 0011 = 0001 = 1
19 & 17 = 0001 0011 & 0001 0001 = 0001 0001 = 17

OR ($\vee$)

1비트 정수에 대해 OR는 아래와 같이 정의됩니다.

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

일반적인 정수에 대해 OR는, 각 비트별로 OR 연산을 수행한 값으로 정의됩니다.

 

5 | 3 = 0101 | 0011 = 0111 = 7
19 | 17 = 0001 0011 | 0001 0001 = 0001 0011 = 19

임의의 자연수 $A, B$에 대해 $A + B = (A \wedge B) + (A \vee B)$가 성립합니다. 증명은 연습문제로 남깁니다. [각주:1]

XOR ($\oplus$)

1비트 정수에 대해 XOR는 아래와 같이 정의됩니다.

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

일반적인 정수에 대해 XOR는, 각 비트별로 XOR 연산을 수행한 값으로 정의됩니다.

 

5 ^ 3 = 0101 ^ 0011 = 0110 = 6
19 ^ 17 = 0001 0011 ^ 0001 0001 = 0000 0010 = 2

LSHIFT, RSHIFT

LSHIFT는 비트를 왼쪽으로 몇 칸씩 미는(shift) 연산을 말합니다. 즉, a << b는 $a \times 2^b$와도 같습니다. 단, int 자료형을 쓸 경우 1을 왼쪽으로 밀어서 최상위 비트에 오게 될 때 부호가 바뀔 수도 있고... 기타 여러 가지 사항을 조심해야 하는 연산자입니다.

RSHIFT는 반대로 비트를 오른쪽으로 몇 칸씩 미는(shift) 연산을 말합니다. 즉, a >> b는 $\lfloor \frac{a}{2^b} \rfloor$와 같습니다. x >> 1은 x / 2와 같은 역할을 하지만, 현대 컴파일러에서는 여러 가지 최적화를 고려했을 때 둘의 속도는 비슷합니다.

 

3 << 2 = 12
17 >> 2 = 4

NOT

정수의 모든 비트를 반전시킵니다. 추가적인 설명은 필요 없을 것 같네요. 예시를 들고 싶지만, sign handling과 같은 민감한 문제가 발생할 수 있기 때문에 예시는 아래와 같이 이진법으로만 보여 드리겠습니다.

 

~1110 = 0001
~0101 = 1010

비트 연산을 이용한 기법

본격적인 이야기에 앞서 말씀드리자면, 여기서는 정말 기초적인 기법만 다룰 것이고, 더 어려운 기법들은 추후에 비트 DP를 설명할 때 다루도록 하겠습니다.

 

이중 부정

비트 연산은 아니지만, 유용한 테크닉이기 때문에 이곳에 서술합니다.

C에서 느낌표(!)는 부정 연산자로 활용되며, True는 False로, False는 True로 바꿔 줍니다.

C에서 True는 1로, False는 0으로 나타나지만, 일반적으로 0이 아닌 모든 값은 True로 취급됩니다.

 

그런데 가끔씩 0, 1이 아닌 정수 값(True)을 0과 1 중 하나로 바꿔야 할 때가 있습니다. 크게 두 가지 방법이 있습니다.

 

  1. x!=0: 직관적이지만 길다.
  2. !!x: 덜 직관적이지만 짧다.

저는 이 중 이중 부정이라고 불리는 !!x를 선호합니다만, 취향 차이이기 때문에 마음에 드시는 것을 선택하면 됩니다.

 

비트가 켜져 있는 지 확인

어떤 수 x에서 k번째 비트($2^k$의 값을 갖는 비트)가 켜져 있는지 확인하기 위해서는,

x & (1<<k)

와 같이 쓰면 됩니다. 만약 0 또는 1로 값을 변환하려면, 앞에서 설명한 이중 부정을 활용하면 됩니다.

 

최하위 비트

어떤 수 x에서 켜져 있는 비트 중 최하위 비트를 구하려면,

x & (-x)

와 같이 하면 됩니다. 이건 상당히 신기해하시는 분이 많을 텐데요, 이유는 2의 보수 표현법과 관련이 있습니다.

 

2의 보수 표현법에서 -x는 x-1의 비트를 모두 반전시킨 것이라고 했습니다. 따라서 x & (-x)에서 어떤 비트가 켜져 있으려면,

  1. x에서 이 비트가 켜져 있고,
  2. x-1에서 이 비트가 꺼져 있다.

위 두 조건을 모두 만족해야 합니다. 어떤 비트가 최하위 비트가 아니라면, 1을 뺐을 때 그 비트는 그대로 1로 유지될 것입니다. 반면 어떤 비트가 최하위 비트라면, 무조건 1에서 0이 될 것입니다. 따라서 위 방식을 이용해 최하위 비트를 구할 수 있습니다.

 

포함 관계

x & y == x

위 식이 만족한다면, x의 비트는 모두 y의 비트에 포함되어 있다고 할 수 있습니다. 이와 같이 비트 연산자를 이용하면 포함 관계도 매우 단순하게 알아낼 수 있습니다.

 

builtin 함수

예를 들어 아래와 같은 문제는 상수 시간 안에 해결하기 힘듭니다.

  1. 어떤 수 x에서 켜져 있는 비트는 총 몇 개인가?
  2. $2^k$가 주어질 때, 정수 $k$의 값은 무엇인가?

이런 문제를 짧은 시간에 해결해 주는 것이 바로 builtin 함수입니다. builtin 함수는 컴파일러에서 제공해, 특수한 방식으로 구현되어 있어 상당히 빠른 시간에 동작합니다.

__builtin_popcount(x)

위 함수는 x를 이진법으로 나타냈을 때, 켜져 있는 비트의 수를 반환합니다.

 

__builtin_ctz(x)

위 함수는 x를 이진법으로 나타냈을 때, 마지막에 연속해 있는 0의 개수를 셉니다. x & (-x)와 기능이 유사하고, 바로 위에서 설명한 2번 문제를 푸는 기능도 수행할 수 있습니다.

 

연습문제

BOJ 11723. 집합 (S5)

 

$1 \le x \le 20$이기 때문에 비트마스킹 기법을 이용해서 풀 수 있습니다. 비트 연산자의 특징을 완벽히 숙지하고 있어야 풀 수 있는 문제입니다. 편의상 $0 \le x < 20$이라고 가정하고 풀겠습니다. 이는 x에서 1을 빼면 쉽게 만들 수 있는 상황입니다.

  • add x: S |= (1<<x)
  • remove x: S &= ~(1<<x)
  • check x: !!(S & (1<<x))를 출력한다.
  • toggle x: S ^= (1<<x)
  • all: S = (1<<20)-1
  • empty: S = 0
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int m;
int state;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); // 입출력 시간을 줄인다.
    cin >> m;
    while(m--){
        string query;
        int x;
        cin >> query;
        if(query[0] == 'c'){ // check
            cin >> x;
            cout << !!(state & (1<<(--x))) << '\n';
        }
        else if(query[0] == 't'){ // toggle
            cin >> x;
            state ^= (1<<(--x));
        }
        else if(query[1] == 'd'){ // add
            cin >> x;
            state |= (1<<(--x));
        }
        else if(query[0] == 'r'){ // remove
            cin >> x;
            state &= ~(1<<(--x));
        }
        else if(query[0] == 'a'){ // all
            state = (1<<20)-1;
        }
        else{ // empty
            state = 0;
        }
    }
}

위 코드에서 x 대신 --x를 넣은 이유는 x에서 1을 빼 주기 위함입니다.

 

BOJ 14569. 시간표 짜기 (S2)

더보기

각 시간의 포함 여부를 비트로 나타냅니다. long long을 이용하면 50개의 비트도 하나의 수로 압축시킬 수 있습니다.

그 다음, 위에서 설명한 포함 관계 판별을 이용해 문제를 풀 수 있습니다.

 

 

  1. 힌트: 각 비트의 개수를 살펴보세요. [본문으로]

'코딩 > 알고리즘' 카테고리의 다른 글

[초급] 그래프  (6) 2020.07.29
[초급] 비트마스크  (5) 2020.07.13
[초급] 백트래킹  (5) 2020.07.08
[초급] 정렬  (2) 2020.07.08
알고리즘 게시글 작성 계획  (4) 2020.07.08
  • 비키라 2020.11.24 16:19 신고

    x+y == (x&y) + (x|y) 이군요! 좋은 글 잘 읽었습니다.

  • 브루님 팬 2021.01.08 22:46

    "C에서 가장 많이 쓰이는 정수 자료형인 int는 32개의 비트를 가지고 있습니다. 따라서 {이 부분 수식이 이상해요.}가지 수를 표현할 수 있습니다. 부호가 없는 정수 자료형 unsigned int 역시 마찬가지로 32개의 비트를 가지고 있지만, 두 자료형이 나타내는 수의 범위는 조금 다릅니다."

  • 브루님 팬 2021.01.08 22:55

    """1비트 정수에 대해 OR는 아래와 같이 정의됩니다.

    A B A|B
    0 0 0
    0 1 {이 부분이 이상해요.}
    1 0 {이 부분도 이상해요.}
    1 1 1
    """

  • 익명의 싸이컴 2021.05.27 16:16

    마침 비트마스킹을 공부하고 있었는데 압도적으로 감사합니다 ㅠㅠ