[C++ STL] bitset

생각보다 매우 많이쓴다

보조 stl로 굉장히 많이 씀

 

비트마스크 풀때 그냥 비트연산보다 얘로 푸는게 훨씬 빠를때도 있음

 

1. DFS/백트래킹이나 BFS 풀때 visited 배열을 방문처리하기 위한 목적으로 함수호출 시 

인자로 넘기는 경우가 많은데 이때 bitset type으로 넘기면 편하다.

 

공간복잡도도 줄어들고 가장 꿀인거는 다 방문했는지 확인하는 함수를 별도로 작성하지 않고

visited.count() 를 사용해서 한번에 함수를 통해 확인할 수 있기 때문이다.

 

2. 이진법 문제에 bitset을 쓰면 편하다(수학 문제에서)

 

bitset은 이진법으로 구현되어 있고

이진법으로 바꿀 수를 bitset의 생성자에 넣음으로써 한번에 이진수를 알아 낼 수 있기 때문이다.

// 0100011
bitset<7> b(35);

// 0001111
bitset<7> b(15);

 

 

3. 2차원 bitset 도 visited로 쓰면 매우 편함

 

bitset<26> words[SIZE];

 

2차원 bitset도 random access 가 된다!

 

그래서 bool visited[SIZE] 이렇게 쓸바에는 그냥 bitset 으로 하는게 좋다

어차피 0 1 로 판단하는 것이기 때문

bitset<SIZE> visited[SIZE];

//random access 가능
visited[5][10] = 1;
visited[0][0] = 0;

 

---

[bitset functions]

	bitset<26> bit; // 0으로 초기화
	bitset<8> bits("10011011"); // 생성자로 초기화

	bit[7] = 1;
	bit[10] = 0; // 배열처럼 참조가능

	bit.count(); // 1로 켜져있는 개수를 반환
    
	bit.flip(); // 말그대로 반전시킴

	bit.any(); // 1이 하나라도 있으면 1 반환
	bit.none(); // 모두 0이면 1 반환
    
    	bitset.reset() // 모두 0 초기화
    
    	bit.set(); // 모두 1 초기화
	bit.set(0); // 모두 0 초기화

		// 바로 입출력 가능
    	cin << bit; 
    	cout << bit;

 

---

비트 연산도 가능

	if (bits & bit)
    
    	if (bits | bit)
    
	cout << (bits & bitset<8>("0000001")) << "\n";