알고리즘 코딩기법 - 6. 상태를 나타내는 값싼 방법(bits)

안녕하세요 17기 조일룡입니다.

이번 포스팅에서는 2진수를 사용하여 상태를 나타내는 기법에 대해서 살펴보겠습니다.

많은 경우에 어떤 상태는 Yes나 No로 나타낼 수 있습니다.
예를 들면 쟁반위에 사과가 있냐/없냐 와 같은 상태가 있을 수 이겠네요. 초기에 쟁반위에 사과, 배, 참외, 수박, 포도가 있었는데 누군가 과일을 먹어서 어떤 것은 없어졌습니다. 이때 가능한 상태는 모두 32(=2^5)가지가 됩니다.

프로그램을 작성하면서 위와 같은 상태를 나타내야 하는 경우는 종종 발생합니다. 그리고 어떻게든 나타내게 되겠지요..
각각의 과일마다 boolean type의 변수를 하나식 만들 수도 있고 좀 더 똑똑한 누군가는 boolean type의 배열을 선언할 수도 있습니다.

오늘 포스팅에서는 bit를 이용하여 이런 상황을 표현하는 방법을 알아보겠습니다.

Bitwise operation

자주 사용하는 bitwise operation은 bitwise and, bitwise or, bitwise complement, bitwise xor 정도가 있습니다.

하나씩 알아보도록 하겠습니당

bitwise AND

bitwise AND는 두 바이너리 표현에 대해서 각 비트의 쌍마다 AND 연산을 합니다.

    0101
AND 0011
  = 0001

C++ 에서 bitwise AND 연산자는 &입니다. 반면 logical AND 연산자는 &&입니다. 사용할 때 주의를 해야겠지요.
bitwise AND 연산은 주로 bitmask를 취할때 사용합니다. 가령 어떤 바이너리에 대해서 첫번째 비트와 세번째 비트를 취하고 싶다면 bitwise AND 0101(2) 를 취하면 됩니다.


bitwise OR

bitwise OR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 OR 연산을 합니다.

    0101
 OR 0011
  = 0111

C++에서 bitwise OR 연산자는 |입니다. 마찬가지로 logical OR연산자인 ||와 혼돈할 가능성이 크니 주의해야겠습니다.
bitwise OR 연산은 바이너리 표현에 플레그(flag)를 추가할때 사용합니다. 각 비트마다 어떤 의미를 부여한 사항에서 첫번째 비트와 세번째 비트에 해당하는 의미가 추가되었다면 원래 상태에다가 새로 추가된 상태를 더해야 합니다. 이때 bitwise OR을 사용합니다.


bitwise XOR

bitwise XOR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 XOR 연산을 합니다.

    0101
XOR 0011
  = 0110

C++에서 bitwise XOR 연산자는 ^입니다. AND나 OR과 다르게 logical XOR 연산자는 c++에 없습니다.
위의 예에서와 같이 bitwise XOR 연산은 바이너리 표현에에서 특정 비트를 토글(toggle)할때 사용합니다. 비트열 중 어떤 상태를 나타내는 비트를 반전시켜줘야 할때 반전 시켜야할 비트만 1로 세팅해놓고 bitwise XOR를 취하면 됩니다.


bitwise NOT(complement)

bitwise XOR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 NOT 연산을 합니다.

NOT 0101
  = 1010

C++에서 bitwise NOT 연산자는 ~입니다. logical NOT 연산자는 !이니 햇갈릴일은 거의 없겠네요
bitwise NOT은 모든 비트를 반전합니다.

참고
http://en.wikipedia.org/wiki/Bit_operation



사과, 배, 참외, 수박, 포도

이제 비트열을 이용하여 과일의 상태를 나타내보도록 하겠습니다. 그리고 배열을 사용한 방법과 비교를 해보도록 하겠습니다


비트에 의미부여

과일의 종류가 5가지 이므로 다섯비트가 필요합니다.
첫번째 비트부터 다섯번째 비트까지 각각 사과, 배, 참외, 수박, 포도가 있는지 없는지 여부를 나타내는 상태라고 생각합시다. 과일이 있으면 그 비트는 1이 되고 비트가 0이면 그 과일이 없다는 것을 의미합니다.

5개의 비트를 저장할 변수가 필요한데 현재 C++에서 int는 32bit 정수형이므로 5개의 과일의 상태를 저장하고도(5bit사용) 27bit나 남으므로 int형을 사용하겠습니다.


초기상태

처음에는 과일이 모두 있으므로 아래와 같이 초기 상태를 설정할 수 있습니다.

int numFruits = 5; // 과일의 수
int bitFruits[] = {(1<<0), (1<<1), (1<<2), (1<<3), (1<<4)}; // 사과, 배, 참외, 수박, 포도를 나타내는 비트
int fruits = (1<<numFruits) - 1; // 모든 과일이 있다

(1 << 5) - 1에 대해 간략히 살펴봅시다.
1을 이진수로 나타내면 00000001(2)입니다. << 5 연산은 이 바이너리를 왼쪽(더 큰 비트쪽)으로 5번 이동합니다. 그럼 00100000(2)가 됩니다. 여기에서 1을 빼면 00011111(2)가 됩니다. 어떤가요? 다섯개의 과일이 모두 있다는 상태가 되었네요

배열버전

const int numFruits = 5; // 과일의 수
bool fruits[numFruits] = {true, true, true, true, true}; // 모든 과일이 있다.

누군가 과일을 먹는다

A가 지나가다 쟁반에 과일이 놓여져 있는 것을 보고 자기가 젤 좋아하는 수박을 먹었습니다. 이를 아래와 같이 코드로 옮길 수 있습니다.

int eatA = bitFruits[3]; // 먹을 과일 -> 수박
fruits &= ~eatA; // A가 과일을 먹음 - 수박을 먹어서 없어짐

bitwise NOT, bitwise AND 연산을 이용하여 수박에 해당하는 비트를 0으로 변환하였습니다.
연산 후 frutis은 10111(2)가 됩니다.

배열버전

int eatA[numFruits] = {false, false, false, true, false}; // 먹을 과일 -> 수박

// B가 과일을 먹음
for (int i = 0; i < numFruits; i++) 
    if (eatA[i] == true)
        fruits[i] = false;

이번엔 B가 지나가다 쟁반을 보았습니다. B는 욕심이 많아서 배, 수박, 포도를 먹으려 합니다. 아래 코드를 봅시다.

int eatB = bitFruits[1] | bitFruits[4] | bitFruits[5]; // B가 먹으려는 과일 - 배, 수박, 포도에 해당하는 비트
int eatByB = fruits & eatB; // B가 실제로 먹는 과일
fruits &= ~eatB; // B가 과일을 먹음

bitwise OR 연산을 이용하여 B가 먹고싶은 과일들의 비트를 만듭니다. 그 후 먹는 것은 A때와 같습니다.
여기에서 수박은 A가 이미 먹었기 때문에 B가 먹을 수는 없습니다. B가 먹을 수 있는 과일은 자기가 먹으려고 하면서 쟁반에 놓여져 있어야 합니다. eatByB는 B가 실제로 먹게되는 과일을 bitwise AND 연산으로 구합니다.

연산후 eatByB와 fruits는 다음과 같습니다.

eatByB = 10111(2) & 11010(2) = 10010(2) -> 배, 포도
fruits = 10111(2) & (~11010(2)) = 10111(2) & 00101(2) = 00101(2) -> 사과, 참외

배열버전

int eatB[numFruits] = {false, true, false, true, true};
int eatByB[numFruits] = {false};

for (int i = 0; i < numFruits; i++)
{     
    // B가 실제로 먹는 과일
    if (fruits[i] && eat[i])
        eatByB[i] = true;

    // B가 과일을 먹음
    if (eat[i] == true)
        fruits[i] = false;
}

어떤 과일이 없어진거지??

A랑 B가 과일을 먹어서 몇개의 과일이 없어진 것을 나중에 알게된 쟁반의 주인은 어떤 과일이 없어졌는지 알고 싶습니다.
쟁반의 주인은 bitwise NOT연산으로 어떤 과일이 없어졌는지 금새 알아차립니다.

int disappeared = ~fruits; // 없어진 과일 -> 배, 수박, 포도

배열버전

int disappeared[numFruits] = {false};
for (int i = 0; i < numFruits; i++)
    if (fruits[i] == false)
        disappeared[i] = true;

사과 마니아 등장

사과를 엄청나게 좋아하는 A씨가 있습니다. A씨는 사과를 너무 좋아해서 쟁반에 사과가 있으면 그 사과를 먹을 것입니다. 반면 쟁반에 사과가 없으면 자기가 가지고 있던 사과를 쟁반에 올려놓는다고 합니다. A씨가 쟁반을 본다면 어떤일이 일어날까요?

if (fruits & bitFruits[0]) // 사과가 있으면
    fruits &= ~bitFruits[0]; // 사과를 먹는다
else // 사과가 없으면
    fruits |= bitFruits[0]; // 사과를 쟁반에 놓는다

배열버전

if (fuits[0] == true) // 사과가 있으면
    fruits[0] = false; // 사과를 먹는다
else // 사과가 없으면
    fruits[0] = true; // 사과를 쟁반에 놓는다.

Bitwiase 표기 vs 배열표기

yes/no로 나타낼 수 있는 일련의 상태가 있을 때, 이 상태를 나타낼 수 있는 두 가지 방법(비트, 배열)에 대해서 간략히 살펴보았는데요.. 구현의 예에서 드러나듯이 bit를 사용하는 방법이 속도, 메모리, 구현 측면에서 모두 배열을 사용하는 방법보다 월등히 뛰어납니다. (물론 제 생각이긴 합니다) 한가지 단점이 있다면 나타내야할 상태의 공간이 크다면(예를 들어 50개 정도되는 상태는 int변수에 담을 수 없으니깐여;;) bit를 사용하기 힘들어 지는데 이때는 다른 방법을 강구해 봐야겠지요.. 배열을 쓰는것도 방법이 될 수 있습니다.

다행이도 long long(__int64) 이라는 타입은 64bit를 지원합니다. 이 타입을 이용하면 64개의 독립된 변수를 가진 상태까진 하나의 변수를 이용하여 나타낼 수 있습니다.



이번 포스팅에서 bit를 이용한 상태표현에 대해서 알아보았으니 다음 포스팅에서는 bit를 이용한 brute force방법에 대해 알아보겠습니다.


ps.
제가 포스팅하는 소스에는 무한버그가 있을 수도 있습니다. -ㅁ-;;