Even Idiots Can Make Game
비트 마스크
#1 C++에서 비트 마스킹
비트 마스킹 문제를 풀면 보통 int 나 long long 처럼 기본 자료형을 사용한다.
하지만 C++에는 이미 비트 단위 연산에 최적화된 std::bitset 클래스 템플릿을 제공하고, 사용법을 조금만 알면 훨씬 편리하고 안전하고, 효율적으로 비트 단위 연산을 수행할 수 있다.
#1
std::bitset이란?
int 나 long long 등을 비트 마스킹 용도로 사용했을 때에는 해당 자료형의 비트 길이를 모두 써야 했는데, bitset을 사용하면 임의의 N 크기를 빌려올 수 있으니 매우 편리하다.
또한, 마치 그 자체가 비트 스트림인 것처럼 기본 논리 연산자와 함께 사용할 수 있으며, 이러한 비트의 나열을 문자열이나 다른 정수형으로 쉽게 변환할 수도 있다.
#1
std::bitset의 기본적 사용법
#2 초기화
// 0b 000'0000
bitset<7> b1;
// 0b 1010
bitset<4> b2{0xA};
// 0b 001
bitset<3> b3{33};
// 0b 0011
bitset<4> b4{"0011"};
// 0b 0000'0110
bitset<8> b5{"ABBA", size_t(4), /*0:*/'A', /*1:*/'B'};
#2 멤버 접근 및 변경
// 예외 처리를 하지 않는 인덱스 접근
b[1] = 1;
// 예외 처리를 하는 인덱스 접근으로, 비트를 1로
b.set(2);
// 전체 비트를 1로
b.set();
// 예외 처리를 하는 인덱스 접근으로, 비트를 0으로
b.reset(2);
// 전체 비트를 0으로
b.reset();
// 전체 비트를 역전시킴
b.flip();
#2 멤버 갯수
// 비트의 크기
b.size();
// true인 것들의 개수
b.count();
#2 멤버십 테스트
// 특정 인덱스의 비트가 1인지 확인
b.test(3); // true
// 하나라도 1이면 true
b.any(); // true
// 전부 0이면 true
b.none(); // false
// 전부 1이면 true
b.all(); // true
#2 다른 자료형으로 변환
// 숫자 값으로 변환
unsigned long x = b.to_ulong();
unsigned long long y = b.to_ullong();
string z = b.to_string();
// 출력
cout << b << '\n';
#1
비트 연산자와 std::bitset
아래 연산자와 아래 연산자를 이용한 복합 비트 연산자는 모두 std::bitset과 함께 쓸 수 있다.
| 연산자 | 의미 |
|---|---|
~ | NOT |
&, &= | AND |
|, |= | OR |
^, ^= | XOR |
<<, <<= | Left Shift |
>>, >>= | Right Shift |
#1 연습 문제
[백준] 13701 G4 중복 제거을 bitset을 활용하여 풀이하면 아래와 같다.
- 최대 $2^{25}$개의 정수를 입력받는데, 이 중에 중복된 수가 있을 수 있다고 한다.
- 입력받은 순으로 출력하되, 중복된 것은 출력하지 않아야 한다.
- 입력되는 정수는 $0$ 이상, $2^{25}$ 미만이라고 한다.
std::bitset을 이용하여, $0$부터 $2^{25}$까지 모든 정수에 대해서 각 정수의 중복 여부를 표시하는 1 비트를 빌려오자.
쉽게 말해, $\verb|bitset<|2^{25}\verb|>|$로 범위 내의 모든 정수에 대응하는 1 비트를 빌려오자는 뜻이다.
$2^{25}$ 비트는 대략 4 MB 을 차지하며, 이는 문제 조건을 넉넉히 통과한다.
코드는 아래와 같다.
| |
#1
bitset을 쓸 때 주의할 점들
#2 1비트에 대한 “진짜 참조"는 없다.
bitset은 내부적으로 보통 unsigned long이나 unsigned long long의 배열로 비트를 관리한다.
bitset<32>{}[31] = true;
위 예제처럼 개별 비트에 대입하는 문법은, 실제로 31번째 비트에 대한 lvalue에 접근하는 것 처럼 보이지만, 하드웨어 메모리는 최소 1바이트 단위로만 주소 접근이 가능하므로, 단일 비트 자체에 대한 포인터나 진짜 참조는 존재할 수 없다.
그래서 std::bitset은 내부적으로 bitset<N>::reference라는 프록시 객체를 사용하여 개별 비트에 대한 읽기/쓰기를 흉내낸다. 이 객체는 실제 참조는 아니며, 해당 비트가 소속된 바이트를 읽고 쓰는 방식으로 작동한다. 이 과정에서 동일한 바이트에 포함된 다른 비트들 함께 읽거나 쓰게 될 가능성이 있다.
즉, b[i] = true는 i번째 비트만 영향을 주는 것 처럼 보이지만, 실제로는 i / 8 번째 바이트 전체가 연산 대상인 것이다.
#2
실제 bitset이 점유하는 공간은 메모리 정렬을 따져 봐야 안다.
sizeof(bitset<25>{}); // 25가 아님!
또한, bitset의 실제 메모리 배치는 내부에서 사용하는 타입(보통 unsigned long)의 정렬 규칙을 따르므로, 예를 들어 bitset<25>는 논리적으로 25비트만 필요하지만, 실제로는 unsigned long 단위로 할당되어 32비트, 혹은 그 이상의 공간을 점유하게 된다.
#2 컴파일 타임에 크기가 고정된 비트 시퀀스에만 쓰자.
bitset은 크기가 컴파일 타임에 고정된 비트 시퀀스를 표현할 때 쓴다.
크기가 런타임에 결정되는 비트 시퀀스의 경우, 다른 구조를 고려하는 것이 더 적절하다.