[Algorithm Tech] Bitmask(비트마스크)

* Bitmast(비트마스크)

정수의 이진수 표현을 자료 구조로 쓰는 기법

특징 : 0과 1을 사용하여 선택/미선택을 판별할 수 있음

장점 : 간결한 코드, 빠른 연산 속도, 적은 메모리 사용

단점 : 순서가 필요한 경우 or 선택/미선택으로 해결되지 않는 문제의 경우 사용 불가

* Bit 연산자

- AND 연산 (기호 : a & b ) : 둘 다 1인 경우에만 결과가 1이 된다.

  ex) 111 & 101 = 101

  ex) 101 & 100 = 100

- OR 연산 (기호 : a | b ) : 둘중에 하나만 값이 1 이면 결과는 1 이 된다.

  ex) 101 | 100 = 101

  ex) 011 | 100 = 111

- XOR 연산 (기호 : a ^ b ) : 둘이 같은 값 (11 or 00) 이면 0 이 되고, 둘이 다른 값 (10 or 01) 이면 1 이 된다.

  ex) 101 | 111 = 010

  ex) 1011 | 0100 = 1111

- NOT 연산 (기호 : ~a ) : 두개의 비트 값에 대한 연산이 아닌 단일 비트값에 대하여 적용하는 연산이다. 각 자릿수를 반대값으로 뒤집는다. 즉, 0 인경우 1로 바꾸고, 1 인 경우 0 으로 바꾼다.

  ex) ~(1011) = 0100

  ex) ~(0011) = 1100

- LEFT SHIFT 연산 (기호 : a << b ) : 값 a 의 모든 각 자릿수의 비트를 좌측으로 b 번 만큼 민다. (우측에는 b개의 0 이 붙는다)

  ex) 1 << 5 = 100000

  ex) 1011 << 2 = 101100

- RIGHT SHIFT 연산 (기호 : a >> b ) : 값 a 의 모든 각 자릿수의 비트를 우측으로 b 번 만큼 민다. (좌측에는 b개의 0 이 붙는다)

  ex) 1101101 >> 2 = 11011

  ex) 110010  >> 5 = 1

* 사용 방법

1의 경우 선택, 0의 경우 미선택이라고 정의했을 때, 8개중 2개를 확인하는 방법

(1 << 0) & 255 != 0    >> 11111111 & 00000001    >> 첫 번째 선택 여부 확인

(1 << 1) & 255 != 0    >> 11111111 & 00000010    >> 두 번째 선택 여부 확인

(1 << 2) & 255 != 0    >> 11111111 & 00000100    >> 세 번째 선택 여부 확인

와 같이 비트연산을 통해 선택 여부를 확인할 수 있다.