[Bitmask] 비트마스크 기초

Bitmask

컴퓨터는 이진번 관련 연산들을 매우 빠르게 진행할 수 있는데, 이러한 특성들을 사용하여 이진수 표현을 자료구조로 사용하는 기법을

비트마스크라고 합니다. 비트마스크는 자료구조라고는 할 수는 없지만 종종 굉장히 유용하게 사용됩니다. 비트마스크를 사용하면 

수행시간이 빨라짐, 간결한 코드, 더 적은 메모리 사용량등 과 같은 장점들이 있습니다.

AND(&)

AND 연산은 두 정수를 한 비트씩 비교하면서 해당 비트가 모두 켜져있을때(1)만 결과비트를 킵니다. 즉 11(2) 10(2)를 AND연산한다면 10(2)의 결과가 나오는 것이죠.

OR(|)

OR 연산은 두개의 비트중 하나만 켜져있어도 결과비트를 키는 연산입니다. 11(2) | 10(2) 의 결과는 11(2)입니다.

XOR(^)

XOR 연산은 두개의 비트가 서로 달라야 결과비트를 키는 연삽입니다. 11(2) ^ 10(2) 의 결과는 01(2)입니다.

시프트연산(<< , >>)

시프트 연산은 해당비트를 왼쪽으로, 오른쪽으로 밀어내는 연산입니다. 1<<2는 0001을 2비트 왼쪽으로 밀어내므로 0100이 됩니다.

* Example 1) 비트마스크를 이용한 집합
* n비트 정수 변수는 0 ~ n-1까지의 정수 원소를 가질 수 있는 집합입니다. 
* 이때 원소 x가 집합에 속해있는지 여부를 알기 위해서는
* 2^x를 나타내는 비트가 켜져있는지 확인하면 됩니다. 
* 예를 들어 {1,4,5,6,7,9}를 표현하는 정수는 정수 754임을 다음과 같이 알 수 있습니다.
* 2^1 + 2^4 + 2^5 + 2^6 + 2^7 + 2^9 = 10 1111 0010(2) = 752(10)
*
* Example 2) 꽉찬 집합 / 공집합 구하기
* 공집합은 너무 간단합니다. 아무것도 없기 때문에 상수 0이 공집합을 나타냅니다.
* 꽉찬 집합도 간단한데 위의 예제에서 볼 수 있듯이 10비트의 꽉찬 집합은 (1<<10)-1을 해주면 됩니다.
* 1을 왼쪽으로 10비트 시프트하면 해당 비트만 1이고 모두 0인데 -1을 해주면 모든 비트가 켜지기 때문입니다.
*
* Example 3) 원소 추가하기
* 원소를 추가하는 방법은 OR연산을 사용합니다. 만약 현재 집합을 tmpset이라고 가정합시다. 
* tmpset집합에 어떤 원소를 추가하고 싶다면 tmpset |= (1<<x) 와 같이 표현할 수 있습니다. 
* 1을 x비트만큼 왼쪽 시프트하면 x번 비트만 켜진 정수가 되는데 이값과 tmpset을 OR연산한다면
* 해당 비트는 반드시 켜지기 때문이죠.
*
* Example 4) 원소 삭제하기
* 원소를 삭제하는 방법은 AND와 NOT연산을 사용합니다. tmpset &= ~(1<<x)와 같이 표현할 수 있는데 
* ~(1<<x)는 해당 비트만꺼지고 모두 1인 값입니다.
* 이 값과 원래 집합을 AND 연산한다면 tmpset의 나머지 비트는 유지되고 x비트만 꺼지게 됩니다.
*
* Example 5) 원소의 포함여부 확인하기
* 만약 해당 집합내에 원소가 포함되어 있는지 알기 위해서는 다음과 같이 알 수 있습니다.
* if(tmpset & (1<<x)) 와 같이 표현하면 1을 x비트만큼 왼쪽 시프트한 결과와 
* tmpset집합의 x번째 비트가 모두 켜져있어야 true를 반환하겠죠.
* tmpset이 1<<x한 비트를 포함하고 있다면 if조건을 통과할 것입니다.
*
* Example 6) 원소의 Toggle
* 해당 비트가 켜져있다면 끄고, 꺼져잇다면 키는 방법입니다. XOR연산이 사용되는데 
* tmpset ^= (1<<x)와 같이 표현할 수 있습니다.
* tmpset의 x번째 비트가 켜져있다면 끄고 꺼져있다면 끌수 있겠죠.