비트마스킹은 메모리와 연산의 효율성을 위해서 정수와 비트연산자를 사용하여 bool 타입의 집합을 표현하거나 상태를 표현하는 구현 기법이다.
비트 연산자
비트 연산(bitwise operation)을 하기 위해서는 비트 연산자에 대한 지식이 필요하다.
연산
두 번째 줄은 bool 집합을 가리키는 정수를 2진수로 표현한 값이다. 오른쪽부터 0번째 인덱스로 본다면 왼쪽으로 갈 수록 인덱스 번호는 증가한다. 각 비트에 대해서 1이면 true 이거나 그 비트에 대한 연관된 값이 on 이다. 반대로 0이면 false 이거나 그 비트에 대한 연관된 값이 off이다.
1. 집합 정의
- 0~32767의 숫자 범위 -> 15 비트 마스크로 해당 숫자 표현 가능
- 2의 거듭 제곱 -> 하나의 원소만 포함된 집합
- 2 의 거듭제곱 - 1 -> 0부터 n - 1 까지 포함된 집합
2. j-th 비트 on
S OR (1 << j) 연산을 이용한다.
3. j-th 비트 확인
S AND (1 << j) 연산을 이용한다.
4. j-th 비트 off
S AND ~(1 << j) 연산을 이용한다.
5. toggle (값 반대로 바꾸기)
S XOR (1 << j) 연산을 이용한다.