비트마스크

bool 배열을 사용하는 것보다 비트 마스크를 사용한 방법이 더 편리한 경우가 있다.

bool arr[10] = {true,false,true,false,true,false,true,false,true,false};
int bitmask = 341; //0b0101010101

위와 같이 10개의 진리 값을 배열과 비트 마스크를 사용해서 나타냈다고 하자. int형은 32비트 길이의 자료형이기 때문에 32개의 요소를 나타낼 수 있지만 첫 10개의 비트만 사용했다. 여기서 모든 진리 값을 반전한다고 해보자. 배열로 나타낸 경우 반복문을 이용해서 각각의 위치에 접근하여 하나하나 바꿔주어야 할 것이다. 그러나 비트 마스크를 사용하여 나타내었다면 NOT연산 하나로 끝낼 수 있다.

// 반복문
for(int i=0;i<10;++i){
    arr[i] = !arr[i];
}

// NOT 연산
bitmask = ~bitmask;

코드가 훨씬 간결하다. 이 글에선 비트 마스크를 조작하는 방법을 다뤄본다.

---

개별 비트 조작

하나의 비트에 대해 적용할 수 있는 방법들이다. 참고로 이글에서 n번째라고 하면 배열에서 처럼 0부터 셈을 했을 때의 위치이다.

 

n번째 비트 1로 만들기

(1 << n)랑 value에 OR연산을 사용한다.

value |=  1 << 5; //value의 5번째 bit는 1이되었다.
cout<< value <<endl;

32

value	0	0	0	0	0	0
1<<5	1	0	0	0	0	0
value | (1<<5)	1	0	0	0	0	0

5번째 bit가 1이 되었다. 5번째 비트가 아닌 다른 비트 값은 0과 OR연산을 하게 됨으로 변화가 없다.

 

n번째 비트 0으로 만들기

!(1 << n)랑 value에 AND연산을 사용한다.

value &= ~(1 << 5); //value의 5번째 bit는 0이되었다.
cout<< value <<endl;

0

value	1	0	0	0	0	0
!(1<<5)	0	1	1	1	1	1
value | !(1<<5)	0	0	0	0	0	0

5번째 bit가 0이 되었다. 5번째 비트가 아닌 다른 비트 값은 1과 AND연산을 하게 됨으로 변화가 없다.

 

n번째 비트 확인하기

value의 5번째 비트와 3번째 비트만 1이고 다른 비트는 0일 때, 5번째 비트의 값을 확인할 수 있을까? (1 << n)랑 value에 AND연산을 사용한다.

cout << (value & (1<<5)) << endl;

32

value	1	0	1	0	0	0
(1<<5)	1	0	0	0	0	0
value & (1<<5)	1	0	0	0	0	0

5번째 비트를 제외한 비트들은 0과 AND연산이 이루어져 모두 0이 된다. 5번째 비트가 1이라면 연산 결과는 0이 아닐 것이고, 비트가 0이라면 결괏값도 0일 것이다.

 

n번째 비트 토글 하기

n번째 비트가 0이면 1, 1이면 0으로 바꿔줄 것이다. (1<<n)과 value에 XOR연산을 사용한다.

value ^= (1<<5);
cout << value << endl;

8

value	1	0	1	0	0	0
(1<<5)	1	0	0	0	0	0
value ^ (1<<5)	0	0	1	0	0	0

5번째 비트가 아닌 비트들은 0과 XOR연산을 하게 됨으로 연산 후에 변화가 없다. 5번째 비트는 1과 XOR연산을 취하기 때문에 5번째 비트가 1이라면 연산 후 5번째 비트는 0, 1이라면 연산 후 0이 된다.

---

여러 비트에 대해 조작

여러 비트에 대해 한번에 조작하는 것 위에서 개별 요소를 다뤘던 것과 크게 다르지 않다.

v1에 v2위치의 모든 비트를 1로 만들기

int v1 = 5; // 0000 0101
int v2 = 112; // 0111 0000
v1 |= v2;
cout << v1 << endl; // 0111 0101

117

 

v1에 v2위치의 모든 비트를 0으로 만들기

// v1 : 0111 0101
// v2 : 0111 0000
v1 &= ~v2;
cout << v1 << endl; // 0000 0101

5

 

v1에 v2위치의 모든 비트 값 확인하기

v1 = 5; // 0101
v2 = 12; // 1100
cout << v1 & v2 << endl; // 0100

4

---

비트마스크를 집합으로 사용하기

집합으로 사용해보자. 집합의 각 원소에 대한 조작은 위에서 말했던 것과 같다.

TODO	How To?
n번째 원소 추가	A |= (1 << n)
n번째 원소 제거	A &= ~(1 << n)
n번째 원소 확인	A &= (1 << n)
n번째 원소 토글	A ^= (1 << n)

집합끼리의 연산도 위에서 사용한 것과 크게 다르지 않다.

TODO	How To?
A , B의 합집합	A | B
A , B의 교집합	A & B
A - B	A & ~B
(A - B) ∪ (B - A)	A ^ B

비트마스크를 집합으로 사용할 때 유용한 몇 가지 스킬들을 더 살펴보자.

 

공집합, n개의 원소가 차있는 집합

2진법으로 1000(2)가 있을 때 1을 빼주면 0111(2)이다. 100000(2) - 1 = 011111(2)이다. 같은 원리로 n개의 원소가 가득 차있는 집합을 비트 마스크로 만들기 위해서는 1<<n에서 1을 빼주어야 한다. 반면 공집합은 그저 0이다.

int full = (1 << n) - 1; // 0111...11
int empty = 0; // 0

 

가장 빠른 위치에 있는 원소 제거

어떤 비트마스크 A가 있다고 하자. n>=0인 모든 n에 대해서 아래 사실이 참이다.

• n > 0인 n에 대해서 A [n] = 1이고 n > k >=0 인 모든 k에 대해서 A [k] =0이다.
• n=0일 때는 0번째 비트가 1이다. (A [0] =1)

그렇다면 이 비트 마스크 A에서 n번째 비트만 0으로 변경하려면 어떤 방법을 사용해야 할까?

n개의 원소가 차있는 집합을 만들었던 방법을 응용하자. 어떤 집합 A가 있다고 하자.

 

0번째 비트가 1인 경우

0번째 비트가 1이라면 A-1은 A에서 0번째 비트가 0이란 것 이외엔 A와 같다. 이때 A & (A-1)을 해주면 A에서 0번째 비트만 0이 된다.

 

n번째 비트가 1이고 이 비트가 비트 마스크의 1인 비트들 중 가장 빠른 위치인 경우

n번째 비트가 가장 1인 빠른 위치에 있다는 것은 0~(n-1) 번째 비트들은 0이라는 뜻이다. 여기서 n을 기준으로 3개의 구간으로 나누어서 확인해보자.

1.  k > n 인 경우 A - 1의 k번째 비트들은 A와 동일하다. (A-1)[k] = A [k] 임으로 (A-1)[k] & A[k] = A [k]이다.
2.  k = n 인 경우 (A - 1)[k] = 0, A [k] =1 이다. (A-1)[k] & A[k] = 0이다.
3.  k < n 인 경우 (A - 1)[k] = 1, A [k] =0 이다. (A-1)[k] & A[k] = A[k] = 0 이다.

k = n인 경우에만 (A-1)[k] & A[k] = 0이고 k가 n이 아닌 경우 (A-1)[k] = A [k]이다. 그래서 A&(A-1)로 가장 빠른 위치에 있는 원소만 제거 가능하다.

int  value = 172; //1010 1100

value &= value-1; //1010 1000 , 168
cout << value << endl;

value &= value-1; //1010 0000 , 160
cout << value << endl;

value &= value -1; //1000 0000 , 128
cout << value << endl;

168
160
128

 

가장 빠른 위치에 있는 원소 확인

가장 빠른 원소를 확인하고 싶을 때도 있다. 이때는 컴퓨터는 음수 표기를 위해 2의 보수법을 사용한다는 점을 이용한다. 어떤 수 a를 2진수로 나타내었을 때 a의 2의 보수는 ~a + 1이다. 위에서 처럼 우리가 찾으려는 위치가 n번째 위치라고 하자. (~A)[n] = 0이고 n > k 인 모든 k에 대해 (~A)[k] = 1이다. 그렇다면 (~A + 1)[n] = 1이고  n > k 인 모든 k에 대해 (~A+1)[k] = 0이 된다. 위에서 처럼 구간을 나누어 생각해보자.

 

•  k > n 인 경우 (~A+1)[k] = ~A [k] 임으로 (~A+1)[k] & A[k] = 0이다.
•  k = n 인 경우 (~A + 1)[k] = 1, A [k] =1 이다. (~A+1)[k] & A[k] = 1 이다.
•  k < n 인 경우 (~A + 1)[k] = 0, A [k] =0이다. (~A+1)[k] & A[k] = A[k] = 0 이다.

그래서 (~A+1) & A의 연산 결과는 A에서 1인 비트들 중 가장 빠른 위치의 비트만 1인 값이고, 이는 -A & A와 연산 결과가 같다.

value = 172; // 1010 1100
cout << (value & ~value+1) << endl;
cout << (-value & value) << endl;

4
4

 

부분집합 여부 확인

집합 A와 집합 B의 교집합이 집합 A일 때 A는 B의 부분집합이다. 이 점을 활용하면 비트 마스크 A가 비트마스크 B의 부분집합인지 간단하게 확인 할 수 있다. (A&B) == A 로 A가 B의 부분집합인지 확인한다. 이때 c++에선 비교연산자(==)가 비트연산자보다 우선순위가 높음으로 이에 주의하자.

int A = 6;  // 0110
int B = 14; // 1110
cout << ((A&B) == A) << endl;
cout << ((B&A) == B) << endl;

1
0

 

부분집합 순회 1

비트마스크 A가 나타내는 집합의 부분집합들을 순회할 때 사용할 수 있는 방법이다.

A = 172; // 1010 1100
for (int subset = A ; subset ; subset = ((subset - 1) & A)){
    cout << subset << endl;
}

172 // 1010 1100
168 // 1010 1000
164 // 1010 0100
160 // 1010 0000
140 // 1000 1100
136 // 1000 1000
132 // 1000 0100
128 // 1000 0000
44  // 0010 1100
40  // 0010 1000
36  // 0010 0100
32  // 0010 0000
12  // 0000 1100
8   // 0000 1000
4   // 0000 0100

 

부분집합 순회 2

어떤 배열이 나타내는 집합의 부분집합들을 비트 연산을 이용하여 순회할 때의 방법이다. 배열의 길이가 n일 때 0에서 2^n-1의 2진법 표현들을 어떤 원소를 선택했다는 표현으로 보면 모든 부분집합을 쉽게 출력할 수 있다. 예를 들어 n = 2 일 때 0~3의 2진법 표현을 보면 00 , 01, 10, 11으로 모든 부분집합의 경우를 보여준다. 이 수들에서 비트가 켜진 여부를 확인하여 부분집합의 원소를 출력하자.

int arr[]={1,2,3,4,5};
int n =5;

for(int i=0; i < (1<<n); ++i){
    for(int j=0;j<n;++j){
        if(i & (1<<j)){
            cout<<arr[j];
        }
    }
    cout<<endl;
}

1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234
5
15
25
125
35
135
235
1235
45
145
245
1245
345
1345
2345
12345