c++ bitset (비트셋) 예제 : 쉽게 이해해 봅시다.

 이번에는 c++에 있는 bitset 이라는 친구에 대해서 잠깐 알아볼 거에요. 보통, 비트 연산자를 이용해서 상태를 관리할 때, & 연산자를 쓰고 <<를 쓰고, >>를 쓰고, | 같은 것을 조합해 가면서 쓰셨을 거에요. 익숙해 지면 그렇게 어렵지는 않습니다만, 그래도 조금 더 쉽게, 집합에 x가 포함되는지, 그렇지 않은지, x를 제거하고, x를 추가하는 연산을 조금 더 간편하게 할 수 있는 방법이 없을까요? 이러한 것들은, bitset을 이용해서 너무 쉽게 할 수 있습니다.

 

 그 전에, 이것이 어떠한 구조를 가지고 있는지 간략하게 살펴 봅시다. 많이 물어보시는 <<와 >>가 내부적으로 어떻게 동작하는지부터 간단하게 소개해 보겠습니다.

 

 

---

 

 먼저 비트셋은 word 단위로 이루어진 배열입니다. 그 안에 상태들이 저장이 되어 있는데요. 우리가 흔히 말하는 int형에다가 뭔가를 섞어놓은 것 같지만, 부호 있는 정수형은, <<나 >> 연산을 수행했을 때, 어떠한 경우에는 행동이 정의되지 않아요. 따라서, 보통은 unsigned형으로 처리합니다.

 

 저는 한 워드당 4bit라고 가정을 하고 그림을 그렸습니다. 실제로는 이것보다는 더 클 거에요.

 

 

 >>연산을 해 봅시다. 여기에서는, 오른쪽 shift를 1만큼 할 거에요. 그러면, 연두색 부분을 우측으로 한 칸 땡겨야 할 거에요. 그러면, value = (value >> 1); 이 될 거에요. 그 다음에, 어딘가에서 상위 비트를 채울 값을 끌어와야 하는데요.

 

 

 빨간색으로 칠한 부분에서 끌어옵니다. 이것을 3번 비트에 넣습니다.

 

 

 그 다음에, 011, 그러니까 연두색으로 칠한 부분을 끌어와야 할 겁니다. 7 ~ 4번째 bit의 값을 value라고 한다면, value를 1만큼 right shift하면 될 겁니다.

 

 

 >> 연산자는 이런 식으로 구현이 되어 있습니다. 그러면 << 연산자는 어떨까요? 뒤에서부터 봅니다.

 

 

 저는 왼쪽으로 2칸 비트를 이동할 거에요. 그러면 먼저, 연두색으로 칠한 것이 2칸 이동할 겁니다. 7 ~ 4번째 상태를 표현하는 값이 v라고 한다면 v = (v<<2)가 될 거에요. 그 다음에, 어떻게 해야 할까요?

 

 

 빨간색으로 칠한 부분을 5 ~ 4번째 bit로 끌고 옵니다. 그리고 나서 어떻게 할 거냐면요. 3 ~ 0번째 상태를 나타내는 bit의 값이 v라고 하면 v = (v<<2)를 할 거에요. 2칸 왼쪽으로 shift 합니다. unsigned이기 때문에, << 연산의 동작 결과는 정의되어 있습니다. 결과 값에서 하위 x비트만 취합니다. 그림에서는 x가 4였기 때문에, 3 ~ 0번째 상태를 나타내는 bit는 각각 0, 1, 0, 0이 됩니다.

 

 

 물론, move 값이 꽤 크다면, 끌어와야 하는 값이 있는 위치도 더 멀어질 거에요. 그 점만 달라요. <<와 >>같은 경우, 복잡도는 O(bit_size/word_size)입니다. 상태 word_size개가 하나의 원소로 압축이 되었기 때문입니다. 대략적인 구조를 이해하셨다면 예제 프로그램을 보도록 하겠습니다.

 

 

---

 먼저 bb.reset()은 모든 bit를 0으로 set 하라는 겁니다. all()과 any(), none()이 있는데요. 이 셋은 각각 모든 비트가 1인가? 1인 비트가 있는가? 그리고 1인 비트가 없는가? 를 리턴해 줍니다. 일단 00000000은 all의 값도, any의 값도 false입니다. none만 true가 나올 거에요.

 

 

 다음에, bb.set()은 모든 비트를 1로 set 하라는 겁니다. 그러면 bb.set()을 수행하고 난 후에, bb는 11111111이 될 겁니다. 그러면 all()은 참이고, any()도 참입니다. 그런데 none()은 거짓입니다. 모든 비트가 켜졌기 때문에, 켜진 비트가 없다는 것을 거짓입니다.

 

 flip은 비트 반전입니다. 정수형 lo를 넣으면 lo번째 bit를 반전시킨다는 의미입니다. 그런데 bb.filp() 이런 식으로 호출할 수도 있어요. 이것은 전체 bit를 반전하라는 겁니다. 크게 어렵지 않지요? bb.filp(2)를 수행한 후에는 11111011이 될 거고요. bb.filp()을 수행한 후에는, 00000100이 될 거에요.

 

 

 그러면 set과 reset도 어떤 비트를 변경시킬건지 넘겨주면 개별적으로 적용될까요? 네. 그렇게 할 수 있습니다. set은 비트를 1로, reset은 0으로 바꾸는 메서드인데요. 00000100에서, bb.set(0)을 해주면, 0번째 bit도 켜질 겁니다. 따라서, bb는 00000101이 됩니다. 그리고 bb.reset(2)는 2번째 비트를 0으로 만들라는 건데요. 그러면 00000001이 되겠죠. test(k)는 k번째 bit가 켜져 있는지를 판단하는 메서드입니다. bb.test(2)는 bb의 2번째 bit가 켜져 있는지를 물어보는 건데요. 꺼져 있어요. 따라서, false가 리턴됩니다.

 

 

 실행 결과값이 이해가 되실 거라고 믿습니다. 사실, bit1.cpp 프로그램만 제대로 이해하셔도, c++의 비트셋을 사용하는데 크게 문제가 없습니다. 그런데, 몇 가지 편리한 것들이 더 있습니다. 이것들도 알려드리도록 하겠습니다.

 

 

---

 

 먼저 대입 연산자를 쓸 수 있어요. bb = 3; 후덜덜합니다. 이 문장을 수행하면, bb의 값이 0...011이 됩니다. 그리고, bitset tt에 bb를 대입할 수 있는데요. 그러면 bb의 내용이 tt에 복사가 되어 버립니다. 즉 tt도 0..011이 됩니다.  그런데, 여기에서 tt의 5번째 bit를 5로 set 하는데요. 그러면 tt의 값이 0..0100011이 될 거에요.

 

 그러면 bb^tt의 값은 어떻게 될까요? 0..0000011과 0..0100011을 xor 시키면 0..0100000이 됩니다. 이것이 cc에요.

 

 

 [] 연산자로 랜덤 접근이 가능해요. dd의 5번째 bit에 1을 넣겠다는 거에요. 그리고 ==과 != 연산자도 있는데요. ==는 내용이 동등한지 비교하는 겁니다. dd는 0..0100000이고 cc 또한 0..0100000이니까 같습니다. 따라서, cc와 dd는 equal 하다는 내용이 출력됩니다.

 

 그러면 <<나 >>, ~, |, &와 같은 연산자도 있을까요? 네. 우리가 배웠던 비트 연산자들은 bitset 내에 모두 구현이 되어 있다고 생각하시면 좋아요. 저는 dd를 오른쪽으로 2만큼 shift를 했는데요. 그러면 dd의 값이 0..010000000이 될 거에요.

 

 

 2번째 예제 프로그램도 그리 어렵지 않네요.

 

 

---

 string이나 char형 배열을 생성자의 매개변수로 넘길 수도 있어요. bb의 값은 00101100, cc의 값은 00001101입니다. 그런데, cc.reset(0)을 하니까 cc의 값은 00001100이 되었습니다. 이를 10진수로 표현하면 12입니다. bitset를 string으로 바꿀 수도 있고, unsigned long형, 혹은 unsigned long long형으로 바꿀 수 있는데, 이 둘은 각각 to_string(), to_ulong()을 호출하면 됩니다.

 

 

 어렵지 않네요. c++에서 비트셋, bitset을 ps에서 쓰신다고 하면 bits1.cpp, 1번 예제만 이해하셔도 무난하실 거에요. 2번, 3번까지 이해하신다면 더없이 좋겠지만, 거기까지 모르셔도 좋습니다. 다만, [] 연산자와 = 연산자, == 연산자 정도가 있다는 것 정도만 이해하고 넘어가셔도 무난할 듯 싶습니다.