비트마스크(BitMask)

비트마스크(BitMask)

비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수(0, 1)로 표현합니다. 이러한 비트의 특성을 이용한 연산을 통해 문제를 해결해 기법을 비트마스크(BitMask)라고 합니다.

이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지입니다.

보통 어떤 비트가 1이면 전구가 "켜져 있다", 0이면 "꺼져 있다"라고 말하며, 전구뿐만 아니라 아래처럼 두 가지 경우로 표현할 수 있는 예시는 모두 가능합니다.

• 의자에 앉으면 1, 서있으면 0
• 남자면 1, 여자면 0
• 정답이면 1, 오답이면 0 

 

사용 이유

비트마스크 기법을 사용하여 문제를 해결하는 큰 이유는 다음과 같습니다.

1. 수행 시간이 빠르다.
2. 메모리 사용량이 적다.

비트마스크 연산은 bit 연산이기에 O(1)의 시간 복잡도를 가지며, 종종 문제를 풀다 보면 비트마스킹 기법을 사용하지 않으면 시간 내에 풀지 못하는 문제들이 존재합니다.

비트마스킹을 활용하여 해결하는 대표적인 문제들은 다음과 같습니다.

1. https://www.acmicpc.net/problem/15787
2. https://www.acmicpc.net/problem/2098
3. https://www.acmicpc.net/problem/1562

 

비트 연산자

비트 연산자는 비트(bit) 단위로 논리 연산을 할 때 사용하는 연산자입니다. 또한 비트 단위로 전체 비트를 왼쪽이나 오른쪽으로 이동시킬 때도 사용합니다.

&	대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산)
|	대응되는 비트 중에서 하나라도 1이면 1을 반환함. (비트 OR 연산)
^	대응되는 비트가 서로 다르면 1을 반환함. (비트 XOR 연산)
~	비트를 1이면 0으로, 0이면 1로 반전시킴. (비트 NOT 연산)
<<	지정한 수만큼 비트들을 전부 왼쪽으로 이동시킴. (left shift 연산)
>>	부호를 유지하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴. (right shift 연산)

 

1. 다음 그림은 비트 AND 연산자(&)의 동작을 나타냅니다.

이처럼 비트 AND 연산자는 대응되는 두 비트가 모두 1일 때만 1을 반환하며, 다른 경우는 모두 0을 반환합니다.

AND( & ) 연산

2. 다음 그림은 비트 OR 연산자(|)의 동작을 나타냅니다.

이처럼 비트 OR 연산자는 대응되는 두 비트 중 하나라도 1이면 1을 반환하며, 두 비트가 모두 0일 때만 0을 반환합니다.

OR ( I ) 연산

3. 다음 그림은 비트 XOR 연산자(^)의 동작을 나타냅니다.

이처럼 비트 XOR 연산자는 대응되는 두 비트가 서로 다르면 1을 반환하고, 서로 같으면 0을 반환합니다.

XOR ( ^ ) 연산

4. 다음 그림은 비트 NOT 연산자(~)의 동작을 나타냅니다.

이처럼 비트 NOT 연산자는 해당 비트가 1이면 0을 반환하고, 0이면 1을 반환합니다.

NOT ( ~ ) 연산

5. 시프트 연산자(<<, >>)의 예제입니다.

<< 연산자는 Left Shift라고 부르며, 모든 비트가 왼쪽으로 정해진 수만큼 이동하는 기능을 수행합니다. 

A << B 라고 표시하며, 'A'를 왼쪽으로 'B' 비트만큼 이동하라는 의미로 사용합니다.

2<<1

>> 연산자는 Right Shift라고 부르며, 모든 비트가 우측으로 정해진 수만큼 이동하는 기능을 수행합니다.

A >> B 라고 표시하며, 'A'를 오른쪽으로 'B' 비트만큼 이동하라는 의미로 사용합니다.

 

16 >> 1

 

 

참고

7편. 연산자 (2)

코딩교육 티씨피스쿨

비트마스크 (BitMask) 알고리즘