Posts [알고리즘 트레이닝] 2장 - 비트마스크, 집합 표현하기, 비트셋(bitset)
Post
Cancel

[알고리즘 트레이닝] 2장 - 비트마스크, 집합 표현하기, 비트셋(bitset)


비트마스크 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++에서 이정도로 간단하게 짤 수 있습니다. 이 문제가 메모리 제한이 있어서 보통 구현처럼 배열, 링크드 리스트 등을 사용하면 실패하는데, 비트셋으로 하면 간단하게 위와 같이 짤 수 있게 됩니다.

알고리즘 - 에라토스테네스의 체 : 소수(prime number)와 소인수분해

[알고리즘 트레이닝] 3장 - 알고리즘의 효율성 추정하기, 최대 부분 배열 합