비트마스킹(Bitmasking)

비트마스킹은 메모리와 연산의 효율성을 위해서 정수와 비트연산자를 사용하여 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) 연산을 이용한다.