개요
프로그래밍을 하다보면 상태를 저장해야할 때가 종종 생긴다.
예를 들면,
내가 주인공 캐릭터가 죽었는지 살았는지를 체크한다거나,
주인공이 공격력 두배 효과를 받고 있다거나,
주인공이 특정 아이템을 갖고 있다거나 등등 …
한 주인공의 상태를 엄청나게 많이 표시해야할 때가 등장한다.
그런데 이 상태들을 표시할 때, 한 상태당 int 하나씩 쓰게 되면 0과 1밖에 쓰지 않는데 불필요한 자원을 쓰게 된다.
그렇다고 0과 1만 쓰는, 1byte도 아닌 1bit 크기의 데이터형식이 존재하지 않는다.
허나 잘 생각해보면, 1bit는 자료형의 기본적인 단위다.
즉, 1bit 크기를 찾을게 아니라, int를 1bit 플래그가 32개 붙어있다고 생각하자는 것이다.
int의 각 비트를 플래그로 생각하자는 이야기이다.▼
위의 개론이 이번 알고리즘의 핵심이다.
비트마스킹은 비트 + 마스킹의 합성어로 비트에 마스크를 씌워 기록한다는 의미이다.
즉, 비트들을 합쳐서 생각하는게 아니라 비트 각각을 보겠다는 의미이다.
동작
그럼 어떻게 플래그를 비트에 기록하고 확인할까?
아래의 값들을 토대로 기록과 확인, 제거를 보자.
#define DEAD 1
#define POWER 2
#define ITEM 4
플레이어 사망: 1 → 000…001
플레이어 파워업: 2 → 000…010
플레이어 아이템 소지: 4 → 000…100
각 값은 각 비트의 자리이기 때문에 2의 제곱수들이다.
플래그 기록
플래그를 기록할 때는 `|`(OR) 연산을 한다.
#define DEAD 1
#define POWER 2
#define ITEM 4
int i = 0;
/*플래그 기록*/
i |= DEAD; // 000...001
i |= POWER; // 000...011
i |= ITEM; // 000...111
OR 연산은 둘 중 하나라도 1이면 1이기 때문에 비어있는 비트에 값을 기록할 수 있다.▼
만약에 이미 채워져있다면, 그대로 1이 나오므로 연산은 무시된다.▼
플래그 확인
플래그 확인은 `&` (AND) 연산으로 한다.
#define DEAD 1
#define POWER 2
#define ITEM 4
int i = 0;
/*플래그 기록*/
i |= DEAD; // 000...001
i |= POWER; // 000...011
i |= ITEM; // 000...111
/*플래그 확인*/
if ((i & DEAD) != 0)
...
if ((i & POWER) != 0)
...
if ((i & ITEM) != 0)
...
만약에 DEAD칸에 비트가 체크되어있다면 절대 0이 나오지 않는다.▼
하지만 DEAD칸에 비트가 체크되어있지 않다면 값은 0이 된다.▼
플래그 제거
플래그 제거는 비트 반전과 `&` (AND) 연산으로 한다.
#define DEAD 1
#define POWER 2
#define ITEM 4
int i = 0;
/*플래그 기록*/
i |= DEAD; // 000...001
i |= POWER; // 000...011
i |= ITEM; // 000...111
/*플래그 확인*/
if ((i & DEAD) != 0)
...
if ((i & POWER) != 0)
...
if ((i & ITEM) != 0)
...
/*플래그 제거*/
i &= ~DEAD; // 000...110
i &= ~POWER; // 000...100
i &= ~ITEM; // 000...000
비트 반전을 했기 때문에 DEAD칸 외의 다른 칸들의 값은 전부 유지되고, DEAD칸만 0으로 바뀐다. ▼
플래그 토글
플래그 토글은 `^` (XOR) 연산으로 한다.
#define DEAD 1
#define POWER 2
#define ITEM 4
int i = 0;
/*플래그 토글*/
i ^= DEAD; // 000...001
i ^= DEAD; // 000...000
XOR 연산은 두 비트가 다를 때 1을, 두 비트가 같을 때 0을 반환한다.
만약 체크가 되어있지 않다면, 기록한다.▼
만약 체크가 되어있다면, 기록을 해제한다.▼
위의 4가지 비트연산을 통해 비트마스킹을 할 수 있다.
마치며
사실 비트마스킹은 알고리즘이라고 하기엔 약간 힘들고, 비트를 이용한 프로그래밍 테크닉이라고 보는게 더 맞다.
아마 C나 C++을 배우다보면 비트 연산에 대해서 배울텐데, 잘 생각해보면 배우고 쓴 일은 거의 없을 것이다.
보통 비트는 low level에서(예를 들면 어셈블리나 CPU, ALU 등등…) 많이 다루고 우리가 이용하는 high level언어들에서는 거의 쓰지 않기 때문이다.
그럼에도 비트 연산을 high level 언어에서 활용하면 효율성이 증가하므로 비트 연산과 비트마스킹에 대해서 알아두면 굉장히 유용하다.
비트 연산도 논리회로에 복잡하게 얽혀 들어가면 어려워지듯이, 비트마스킹도 자체는 쉽지만 다른 알고리즘들과 섞이면 굉장히 어려워진다.
쓰기 조금 어렵다는 점이 있지만, 잘 알아두면 여러모로 데이터를 아끼며 유용하게 잘 사용할 수 있다.