[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';

}