컴퓨터는 본질적으로 0과 1이라는 두 가지 상태(Bit)만을 이해하는 기계입니다. 우리가 일상적인 프로그래밍에서 수백 개의 불리언(Boolean, 참/거짓) 데이터를 다루기 위해 배열(Array)을 선언할 때, 이를 하나하나 메모리에 올리면 적지 않은 공간과 시간이 낭비됩니다. 만약 "전구 10개가 켜져 있는지 꺼져 있는지"의 복잡한 상태를 불리언 배열 대신 단 하나의 정수(Integer) 숫자로 압축해서 표현하고 제어할 수 있다면 어떨까요? C++이나 Java에서 정수 하나는 보통 32비트(4바이트)이므로, 정수 변수 딱 하나만 선언해도 무려 32개의 켜짐/꺼짐 상태를 동시에 저장하고 조작할 수 있습니다. 이렇게 컴퓨터의 가장 낮은 레벨인 비트 연산을 활용하여 집합(Set) 데이터를 경이로운 속도와 최소한의 메모리로 다루는 고급 테크닉을 '비트마스크(Bitmask)'라고 부릅니다. 외계어처럼 보이는 비트 연산자의 원리와 그 강력한 실무 활용법을 완벽히 분석해 봅니다.
1. 비트 연산자의 기초와 마스킹(Masking)의 원리
비트마스킹을 자유자재로 다루려면 5가지의 기본 비트 논리 연산자와 시프트(Shift) 연산을 이해해야 합니다.
- AND (
&): 두 비트가 모두 1일 때만 1을 반환합니다. (특정 비트가 1로 켜져 있는지 확인할 때 씁니다.) - OR (
|): 두 비트 중 하나라도 1이면 1을 반환합니다. (특정 비트를 1로 강제로 켤 때 씁니다.) - XOR (
^): 두 비트가 서로 다를 때만 1을 반환합니다. (특정 비트의 상태를 0은 1로, 1은 0으로 반전시킬 때 씁니다.) - NOT (
~): 비트 전체를 반전시킵니다. 0은 1로, 1은 0으로 모조리 바꿉니다. - Shift (
<<,>>): 비트를 왼쪽이나 오른쪽으로 밀어냅니다.1 << 3은 이진수 1을 왼쪽으로 3칸 밀어1000(2), 즉 십진수 8을 만듭니다. (원하는 위치에 1을 세팅하는 비트마스크의 핵심 기술입니다.)
2. 배열을 대체하는 집합 조작의 마법
어떤 피자 가게에서 0번(페퍼로니), 1번(치즈), 2번(올리브), 3번(베이컨) 토핑의 추가 여부를 관리한다고 해봅시다. 치즈(1번)와 베이컨(3번)을 추가한 상태는 배열을 쓸 필요 없이 이진수로 1010(2), 즉 십진수 10이라는 숫자 하나로 완벽히 표현됩니다.
2-1. 비트마스크 실전 코드 테크닉
현재 토핑 상태를 담고 있는 정수 변수를 S라고 할 때, 비트 연산을 통한 조작은 배열이나 리스트 함수를 부르는 것보다 수십 배 이상 빠릅니다.
- 추가하기 (Add): 2번(올리브) 토핑을 새로 추가하려면 OR 연산을 씁니다.
S = S | (1 << 2) - 제거하기 (Remove): 1번(치즈) 토핑을 빼려면 해당 비트만 0으로 만들고 나머지는 훼손 없이 유지해야 하므로 AND와 NOT을 절묘하게 조합합니다.
S = S & ~(1 << 1) - 포함 여부 확인 (Check): 3번(베이컨) 토핑이 들어있는지 확인하려면 AND 연산 후 그 결과가 0인지 아닌지 봅니다.
if ((S & (1 << 3)) != 0) { // 포함되어 있음 } - 토글 (Toggle): 0번(페퍼로니)이 있으면 빼고, 없으면 넣는 스위치 기능을 하려면 XOR 연산을 씁니다.
S = S ^ (1 << 0)
3. 왜 비트마스크를 써야 할까? (동적 계획법 최적화)
코딩 테스트에서 비트마스크가 선택이 아닌 필수로 쓰이는 영역이 있습니다. 바로 외판원 순회(TSP, Traveling Salesman Problem)처럼 방문한 도시들의 목록을 계속해서 기억하고 다음 함수로 넘겨주어야 하는 '상태 동적 계획법(State DP)' 문제입니다.
만약 15개의 도시 중 1번, 4번, 7번 도시를 방문했다는 상태를 다음 재귀 함수에 넘겨주려면 크기가 15인 불리언 배열을 통째로 복사해서 넘겨주어야 하므로 엄청난 메모리와 시간이 소요됩니다. 하지만 비트마스크를 쓰면 000000010010010(2), 즉 정수 하나만 인자로 던져주면 끝납니다. 상태를 메모리(DP 배열의 인덱스)에 저장할 때도 1차원 배열 자체가 인덱스로 들어갈 수 없으므로, 정수 형태의 비트마스크 값 자체가 곧바로 1차원 배열의 인덱스로 사용되어 코드의 복잡도와 메모리 사용량을 극한으로 줄여주는 구세주 역할을 합니다.
1. 비트마스크(Bitmask)는 이진수의 0과 1 비트를 활용하여 다수의 참/거짓 집합을 단 하나의 정수로 표현하고 조작하는 극한의 최적화 기법입니다.
2. 시프트(
<<) 연산과 AND, OR, XOR, NOT 논리 연산자를 조합하여 데이터의 삽입, 삭제, 조회, 반전을 O(1)의 하드웨어 수준 속도로 처리합니다.3. 복잡한 방문 이력이나 상태를 불리언 배열 대신 정수값 하나로 압축할 수 있어, 메모리 제한이 빡빡한 상태 기록 동적 계획법(DP) 문제에서 필수적으로 요구됩니다.