[이론] 비트마스크(Bitmask)

 

비트마스크는 주어진 문제를 효율적으로 해결하기 위한 강력한 도구로, 특히 상태를 간단하게 표현하거나 부분 집합을 다룰 때 유용하다. 코딩 테스트에서는 메모리와 연산 시간을 절약할 수 있어 많이 활용되며, 비트 연산의 기본 개념만 이해해도 문제 해결에 큰 도움이 된다. 이번 글에서는 비트마스크의 기본 원리와 활용 예제를 통해 그 응용법을 살펴보겠다.

 

---

비트마스크(Bitmask)란?

 

비트 마스크: 비트 연산을 사용하여 데이터를 효율적으로 처리하는 기법

 

보통 상태를 표현하거나 조작할 때 유용하며, 특히 메모리를 절약하고 빠른 계산을 필요로 하는 상황에 유용하다. 이진수의 각 비트를 이용하여 여러 상태를 표현한다. 그래서 int형 value 하나로 32개의 Boolean 상태를 표현할 수 있다.

이러한 구조를 통해 원하는 데이터를 추출할 수 있도록 마스킹한다.

 

※. long형은 64개의 Boolean 상태를 표현할 수 있다.

 

💡 비트마스크는 부분 집합 문제, 그래프 탐색, 상태 전이 등 다양한 문제를 해결하는데 사용된다.

💡  코딩 테스트에서는 N이 20보다 작을 때, 그리고 조합 문제에서 사용될 수 있다.

 

 

---

비트 연산의 종류

index 번째 비트가 켜져 있는지 확인	if (value & (1 << index))
index 번째 비트 켜기	value |= (1 << index)
index 번째 비트 끄기	value &= ~(1 << index)
index 번째 비트 XOR	value ^= (1 << index)
n 자리 만큼 비트가 켜지도록 설정	value = (1 << n) - 1
최하위로 켜져있는 비트 찾기	index = (value & ~value)

 

비트마스크는 비트를 기반으로 연산을 수행하기 때문에 &, |, ^ 연산에 대해 지식이 있어야 한다.

위 연산은 코딩 테스트에서 많이 사용하는 구문이므로 원리를 이해하고 외우면 좋다.

 

 

 

---

비트마스크 장단점

 

비트마스크는 다양한 문제에서 유용하게 활용될 수 있는 도구지만, 그만큼 장단점도 명확하다.

 

비트마스크 장점

• 메모리 절약: 비트마스크는 데이터를 효율적으로 압축하여 표현한다. Boolean 배열 32개의 메모리는 4-byte * 32 만큼 메모리를 사용한다. 하지만 비트마스크를 사용하면 Int 1개 메모리를 사용하므로 4-byte * 1 만큼 메모리를 사용하므로 32배 절약할 수 있다.
• 빠른 연산: 비트 연산이기에 CPU 처리 속도가 매우 빠르다.
• 상태 관리의 간결함: Int 하나로 통합하여 관리하기 때문에 간결하다.

 

비트마스크 단점

• 가독성 부족: 비트를 사용하기 때문에 개발자 입장에선 코드 가독성이 떨어질 수 있다.
• 디버깅 어려움: 각 비트가 의미하는 것이 직관적으로 드러나지 않아 디버깅이 어렵다.
• 제한된 크기: Int는 32개, Long은 64개 까지의 상태만 담을 수 있기에 확장성이 떨어진다.

 

 

 

---

게임 개발 활용: 버프 관리 시스템

 

 

옛날에 게임 개발을 하면서 '버프 관리 시스템'을 제작한 적이 있었다.

 

유저 DB에 포함된 버프 ON/OFF 유무 정보

 

 

게임에 존재하는 버프는 약 20여개이다.

처음에는 Boolean 배열을 생성해서 서버와 API 통신을 주고 받았다.

그런데 비트마스크를 배우고 난 뒤 Int 값 하나로 표현이 된다는 사실을 깨달았다.

 

이때까지 나는 이런 사실을 몰라서 서버 비용을 절약하지 못했다...

 

 

 

그래서 버프 관리 시스템을 코드로 적용해봤다.

HP 및 MP 버프에는 [ 고급, 중급, 초급 ] 3가지 형태의 종류를 가진다.

그래서 위처럼 각 버프에 맞는 비트마스크를 생성하여 현재 버프 상태를 체크한다.

 

 

예시 코드

	int buff_flag = 1 + 4 + 16;
	int buff_HP_bitmask = 1 + 2 + 4; // 최하위부터 1,2,3 bit
	int buff_MP_bitmask = 8 + 16 + 32; // 최하위부터 4,5,6 bit

	// Server에서 버프 관련 bit 데이터 받아오기
	// buff_flag = Backend.GetUser.GetBuf();

	// HP 버프 체크
	int HP_check = (buff_flag & buff_HP_bitmask);
	for (int i = 0; i < 3; i++)
	{
		if ((HP_check >> i) & 1)
			// i + 1 번째 HP 버프 상태 ON
		else
			// i + 1 번째 HP 버프 상태 OFF
	}

	// MP 버프 체크
	int MP_check = (buff_flag & buff_MP_bitmask);
	for (int i = 3; i < 6; i++)
	{
		if ((MP_check >> i) & 1)
			// i - 2 번째 MP 버프 상태 ON
		else
			// i - 2 번째 MP 버프 상태 OFF
	}

 

---

게임 개발 활용: 캐릭터 상태 관리

 

비트마스크를 통해 캐릭터의 상태를 관리할 수 있다. 열거형(Enum)에 [ Flags ] Attribute를 추가하여 비트 단위로 결합하여 조합할 수 있다. 이를 통해 메모리를 절약하고 코드를 간결하게 만들 수 있다.

💡 Enum 값은 shift 연산을 통해 하나의 bit 값만 가지도록 할당해야 한다.

 

 

 

예시 코드

[System.Flags]
public enum CharacterState
{
    None = 0,          // 0000
    Running = 1 << 0,  // 0001
    Jumping = 1 << 1,  // 0010
    Shooting = 1 << 2, // 0100
    Crouching = 1 << 3 // 1000
}

public class Character : MonoBehaviour
{
    public CharacterState state;

    void Update()
    {
        // 상태 추가: 캐릭터가 점프 중이면서 쏘고 있을 때
        state |= CharacterState.Jumping | CharacterState.Shooting;

        // 상태 제거: 캐릭터가 점프 상태 해제
        state &= ~CharacterState.Jumping;

        // 상태 확인: 캐릭터가 쏘고 있는지 여부 확인
        if ((state & CharacterState.Shooting) == CharacterState.Shooting)
        {
            Debug.Log("Character is shooting!");
        }
    }
}

 

 

 

---

정리

 

정리하자면 비트마스크는 상태를 효율적으로 관리하고 빠르게 처리해야 하는 문제에서 주로 사용된다. 처음에는 비트마스크에 적응하기 어렵지만 플래그들을 관리하는 유용한 도구이므로 배워두면 좋다고 생각한다.