
비트마스킹(BitMasking)
정수의 이진 표현을 이용해 특정 비트(bit)를 조작하거나 검사하는 기술
0과 1로 구성된 이진수 표현에서 원하는 자리의 비트를 다루는 방법
플래그 관리, 퍼미션 설정, 효율적인 상태 추적 등에 사용된다.
*플래그 관리 : 여러 개의 상태/옵션 중 일부가 켜져 있는지
예를 들어, 게임에서 캐릭터에게 여러 상태(중독, 화상, 빙결, ...) 효과가 동시에 걸릴 수 있고,
중독 : 1 << 0 -> 1 / 화상 : 1 << 1 -> 2 / 빙결 : 1 << 2 -> 4 의 값이라 가정하면
let status = 0; | |
status |= 1; // 중독 상태 추가 | |
status |= 4; // 빙결 상태 추가 | |
// 중독 상태 확인 | |
if (status & 1) console.log("중독 상태입니다."); | |
// 빙결 상태 제거 | |
status &= ~4; |
위 코드와 같이 여러 상태를 숫자 하나로 압축해서 관리할 수 있다.
*퍼미션 설정 : 누가 어떤 권한을 가지고 있는가
예를 들어, 파일에 대해 읽기, 쓰기, 실행의 권한이 있고,
읽기 : 1 << 0 -> 1 / 쓰기 : 1 << 1 -> 2 / 실행 : 1 << 2 -> 4 의 값이라 가정하면
let permission = 0; | |
permission |= 1; // 읽기 권한 추가 | |
permission |= 2; // 쓰기 권한 추가 | |
// 실행 권한 있는지 확인 | |
if (permission & 4) { | |
console.log("실행 가능"); | |
} else { | |
console.log("실행 불가"); | |
} |
위 코드와 같이 권한 설정을 할 수 있고, 권한이 많아질수록 비트로 표현하면 코드가 짧아지고 빨라지며 효율적이다.
*효율적인 상태 추적 : 많은 상태를 빠르게 저장하고 조회
여러 정점을 방문하는 그래프 탐색 알고리즘(DFS, 백트래킹, ...) 등에서 사용할 수 있고,
예를 들어, N=4개의 노드를 방문한다고 가정하면,
0000 -> 아무 노드도 방문하지 않음 / 1010 -> 1번, 3번 노드를 방문했음
위와 같이 사용할 수 있고, 배열 대신 비트로 방문 여부를 추적하기 때문에 더 빠르고 적은 메모리를 사용한다.
비트마스킹의 장점
1. 메모리를 절약할 수 있다.
배열이나 객체 대신 숫자 하나에 여러 상태를 압축해서 담을 수 있다.
여러 상태를 숫자 1개로 저장한다.
2. 상태 확인 및 변경이 매우 빠르다.
&, |, ^, ~ 같은 비트 연산은 하드웨어 수준에서 매우 빠르게 처리된다.
비트 연산은 O(1)로 매우 빠르다.
3. 코드가 간결해진다.
On/Off 개념이 뚜렷해서 특정 상태 조작이 직관적이다.
조건문, 토글, 포함 여부 등의 로직이 깔끔하고 간단하다.
자주 쓰는 비트 연산자
연산자 | 이름 | 설명 | 예시(a=0101, b=0011) |
& | AND | 두 비트가 모두 1일 때만 1 | a & b = 0001 |
| | OR | 하나라도 1이면 1 | a | b = 0111 |
^ | XOR | 서로 다르면 1 | a ^ b = 0110 |
~ | NOT | 비트를 반전 | ~a = 1010 |
<< | 왼쪽 시프트 | 비트를 왼쪽으로 밀기 (곱셈 효과) |
a << 1 = 1010 x << n = x * 2^n의 값과 같음 |
>> | 오른쪽 시프트 | 비트를 오른쪽으로 밀기 (나눗셈 효과) |
a >> 1 = 0010 x >> n = Math.floor(x / 2^n)의 값과 같음 |