비트마스크 1 « k 는, k번째 위치에만 비트 1이 있고, 나머지 위치에는 비트 0이 있는 정수입니다.
그러므로 이 비트마스크를 사용하면 어떤 정수의 특정한 비트 하나에 접근할 수 있습니다.
예를 들어 x & (1 « k) 가 0이 아니라면, 정수 x 의 k번째 비트가 1이라는 의미입니다.
1
2
3
4
01001
&01000 (1 << 3)
-------
01000 => not 0 => // 01001(정수 9)의 3번째 비트는 1이다.
이와 비슷한 아이디어를 사용하면, 위처럼 특정 번째의 비트가 1인지 아닌지 판단하는 것 외에도
- 특정 번째의 비트 하나를 1로 바꾸거나, 0으로 바꾸거나, 반대로 뒤집을 수도 있습니다.
1
2
3
4
x&(1 << k) // 정수 x의 k번째 비트가 1인지 아닌지 판단한다. (0이 아니면 1이라는 의미)
x|(1 << k) // 정수 x의 k번째 비트를 1로 바꾼다.
x&~(1 << k) // 정수 x의 k번째 비트를 0으로 바꾼다.
x^(1 << k) // 정수 x의 k번째 비트를 뒤집는다.
비트마스크 1 « k는 항상 int형이므로, long long형 비트마스크를 사용하려면 1LL « k 로 씁니다.
- 참고 : XOR 연산(^)은 a ^ b 에서 a나 b 둘 중 하나만 1일 경우에 결과 1을 반환합니다.
집합 표현하기
위에서 다룬 비트마스크로 집합 표현하기에 활용할 수 있습니다.
예를 들어, int형 정수(32bit)로 집합의 원소를 표현한다면 다음과 같습니다.
1
00000000...0000010011010 // {1,3,4,8} 집합을 표현한 것
즉, 1, 3, 4, 8번째 비트가 1인 것을 {1, 3, 4, 8} 집합으로 나타낸 것입니다.
집합으로 나타낸 이후, 집합에 포함된 원소를 모두 출력하려면 다음과 같이 비트마스크를 사용합니다.
1
2
3
for(int i = 0; i < 32; i++){
if(x&(1<<i)) printf("%d ",i);
}
c++ 비트셋
c++에서는 표준 라이브러리로 비트셋(bitset)이라는 자료 구조를 제공합니다.
비트셋은 원소가 0 또는 1인 배열처럼 쓸 수 있습니다.
c++에서 제공하는 비트셋이 유용한 이유는, 0과 1을 사용한 비트를 활용해야 할 때 bitset을 사용하면 제공하는 함수들로 다양한 기능을 손쉽게 사용할 수 있기 때문입니다.
비트 연산도 비트셋에 대해 그대로 적용할 수 있습니다.
1
2
3
4
5
6
7
8
9
bitset<10> s;
s[0] = 1;
s[1] = 2;
cout << s[1]; // 1
cout << s[5]; // 0
...
bitset<10> a, b;
bitset<10> c = a & b;
...
다음은 다양한 비트셋 관련 함수들입니다.
reset(): 모든 bit를 0으로 set 하는 함수reset(n): n번째 bit를 0으로 set 하는 함수
set(): 모든 bit를 1로 set 하는 함수set(n): n번째 bit를 1로 set 하는 함수
all(): 모든 bit가 1인가? 를 판별하는 함수any(): 1인 bit가 하나라도 있는가? 를 판별하는 함수none(): 1인 비트가 한 개도 없는가? 를 판별하는 함수
flip(n): n번째 bit를 반전시키는 함수 (n은 정수)flip(): 모든 bit를 반전시키는 함수
- 비트셋끼리의 대입도 가능하다.
1
2
3
4
5
bitset <10> aa;
bitset <10> bb;
...
aa = 3;
bb = aa; // bb에는 aa의 값인 000...011 이 들어간다.
- 비트셋의 생성자에 문자열을 넘길 수 있다. 해당 문자열대로 비트셋이 만들어진다.
- 비트셋에 to_string을 사용할 수 있다. 그 비트열 그대로 문자 형태로 만들어낼 수 있다.
1
2
3
4
5
bitset <8> aa;
aa = bitset<8>("01011001"); // aa에는 01011001 이라는 비트 값이 들어간다.
...
cout << aa.to_string(); // "01011001"이 출력된다.
unsigned long test = aa.to_ulong(); // 01011001 값이 unsigned long 타입 변수에 들어간다.
- 비트셋으로 쉽게 풀 수 있는 백준 문제
- https://www.acmicpc.net/problem/13701 : 중복 제거(13701번)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <string>
#include <iostream>
#include <bitset>
using namespace std;
bitset<(1 << 25)> bits;
int main() {
int input;
while (scanf("%d", &input) != EOF) {
if (bits[input] == 0) {
bits[input] = 1;
printf("%d ", input);
}
}
return 0;
}
- c++에서 이정도로 간단하게 짤 수 있습니다. 이 문제가 메모리 제한이 있어서 보통 구현처럼 배열, 링크드 리스트 등을 사용하면 실패하는데, 비트셋으로 하면 간단하게 위와 같이 짤 수 있게 됩니다.