[C++] STL 자료구조: bitset
bool 자료형은 0 또는 1을 저장하지만, 1byte = 8bit의 저장공간을 사용한다. 이유는 cpu가 자료형을 할당할 때 바이트 단위로 주소를 지정하기 때문이다
bitset은 이렇게 낭비되는 7bit를 없애기 위해서 0, 1을 하나 당 1bit에 저장하는 자료형이다. bitset을 bool []이나 vector<bool> 대신 이용하면 메모리를 1/8만 사용하면서 여러 유용한 기능을 사용할 수 있다.
bitset은 연속된 메모리 공간을 잡아둔 뒤, 비트 연산을 통해 bit 단위로 값들을 저장하는 방식으로 구현되어있다.
메모리 공간의 각 칸들은 구현마다 다르겠지만 보통 32bit 또는 64bit로 이루어져있으며, 따라서 32 또는 64개의 bitset 칸들을 연산 하나로 한 번에 처리할 수 있다. 이런 이유로 bitset의 멤버 함수 또는 연산자의 시간복잡도는 O(n/32) 또는 O(n/64)와 같은 형태이다.
bitset은 일반적으로 bool []이나 vector<bool>을 사용해야하는 곳에 대신 사용하면 좋다.
하지만 bitset은 컴파일 타임에 배열의 크기를 지정해줘야한다. 따라서 만약 배열의 크기를 바꾸거나 런타임에 크기를 지정해야 한다면 vector<bool>을 사용하면 되고, 아니라면 bitset을 사용하면 된다.
<생성자> 컴파일 타임에 배열의 크기를 지정해줘야 한다
int main() {
fastio;
bitset<10> B1; // B1 = "0000000000"
bitset<10> B2(13); // B2 = "0000001101"
bitset<10> B3("1011"); // B3 = "0000001011"
cout << B1 << '\n' << B2 << '\n' << B3 << '\n';
}
<멤버 함수>
int main() {
fastio;
bitset<100> B; //
B.set(); cout << B.count() << '\n'; // 100 ; set: 모든 비트를 1로
B.reset(); cout << B.count() << '\n'; // 0
cout << B.size() << '\n' << '\n'; // 100
B[2] = 1; // B = "...100"
cout << B.count() << '\n'; // 1
cout << B.any() << '\n'; // 1 ; bitset내에 켜진 비트가 존재하는지 여부를 bool 자료형으로 반환
cout << B.all() << '\n'; // 0; bitset내에 모든 비크가 켜져있는지 여부
cout << B.none() << '\n' << '\n'; // 0 ; bitset내에 모든 비크가 꺼져있는지 여부
B[2].flip(); // B = "...000"; flip == 1->0 0->1로 바꾸기
cout << B.count() << '\n'; // 0
cout << B.any() << '\n'; // 0
cout << B.all() << '\n'; // 0
cout << B.none() << '\n' << '\n'; // 1
B[1] = B[3] = B[4] = 1;
string s = B.to_string();
cout << s << '\n'; // ...11010
}
<비트 연산자> == size가 같은 두 bitset끼리만 가능
int main() {
fastio;
bitset<5> B1("01011");
bitset<5> B2("00111");
cout << (B1 & B2) << '\n'; // 00011
cout << (B1 | B2) << '\n'; // 01111
cout << (B1 ^ B2) << '\n'; // 01100
cout << (B1 << 2) << '\n'; // 01100
cout << (B1 >> 2) << '\n'; // 00010
cout << ~B1 << '\n'; // 10100
}
<bit 상태 출력>
int main() {
fastio;
for (int i = 0; i < 32; i++) {
cout << i << ' ' << bitset<6>(i) << '\n';
}
} 하면
0 000000
1 000001
2 000010
3 000011
... 31까지 간다.
백준
11723번)
// #include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int main() {
fastio;
bitset<21> a; // 선언 위치에 주의하자, while문 안에 선언하면 안 된다.
int n; cin>>n;
while(n--){
string s; int i;
cin>>s;
if(s== "add") {cin>>i; a[i]=1;}
else if (s=="remove") {cin>>i; a[i]=0;}
else if (s=="check") {cin>>i; cout<<a[i]<<'\n';}
else if (s=="toggle") { cin>>i; a[i].flip();}
else if (s=="all") {a.set();}
else a.reset();
}
}
1269번) a와 b의 차집합 구하기
on / off 처럼 동작해야할 경우 bitset을 쓰는 것도 나쁘지 않다.
a입력 받고 b입력 받으므로 그냥 합쳐서 n+m으로 작성
bitset<100'000'001> BIT;
int main() {
fastio;
int n, m; cin >> n >> m;
for (int i = 0; i < n + m; i++) {
int t; cin >> t;
BIT[t].flip();
}
cout << BIT.count() << '\n';
}
13701번)
bitset<1 << 25> BIT;
1을 왼쪽으로 25번 시프트한 값(즉, 2^25)을 갖는 비트셋을 선언한다.
여기서 << 연산자는 왼쪽으로 비트를 이동시킨다. 따라서 1 << 25는 1을 이진수로 표현했을 때 25번째 비트를 1로 만들고, 나머지 비트들은 모두 0으로 만든다. 이것은 2의 25승과 동일한 값을 가진다.
bitset<1<<25>BIT;
int main() {
fastio;
for(int n; cin>>n;){
if(BIT[n]) continue;
cout<<n<<' '; BIT[n]=1;
}
cout<<'\n';
}