비트마스크, 비트마스킹(BitMasking)이란

1.비트마스킹(BitMasking)이란

비트(bit, binary digit)란 컴퓨터의 최소 연산 단위로, 하나의 bit가 표현할 수 있는 경우는 0과 1로 두 가지이다. 주로 1은 켜져있고, 0은 꺼져있다고 표현한다. 비트 마스킹이란, 정수를 이진수로 표현하여, 비트 연산을 통해 문제를 해결하는 알고리즘 테크닉이다.

 

5개의 전구의 상태(켜짐/꺼짐)를 표현할 때 다음과 같은 방식들을 이용할 수 있다. 우선 다음과 같이 리스트 자료형으로 표현할 수 있다.

lights = [True,True,False,False,False]

(Python에서 2진수를 표현할때 다음과 같이 앞에 0b를 붙인다.)

lights=0b11000

• 삽입,삭제,조회가 빠르다
• 정수 표현으로 DP(Dynamic Programming) 문제 해결이 가능하다
• 간결한 코드 작성에 용이하다

2.비트 연산

비트 연산에 대해 알아보자

 

1. AND 연산(&)

대응하는 bit가 모두 1일 경우 1을 반환, 아닐 경우 0을 반환한다.

1010 & 1100 = 1000

    1010

    1100

 &---------

    1000

2. OR 연산(|)

대응하는 bit가 하나라도 1일 경우 1을 반환, 아닐 경우 0을 반환한다.

1010 | 1100 = 1110

   1010

   1100

| -------

   1110

 

3. XOR 연산(^)

대응하는 bit가 다를 경우 1을 반환, 같을 경우 0을 반환한다.

1010 ^ 1100 = 0110

   1010

   1100

^ -------

   0110

 

4. NOT 연산(~)

bit의 값을 반전하여 1일 경우 0을 반환하고, 0일 경우 1을 반환한다.

~1010 = 0101

   1010

~ -------

   0101

 

5. Shift 연산(<<,>>)

*왼쪽 Shift연산(<<) : 왼쪽으로 bit를 옮긴다. 빈자리는 0으로 채워진다.

0011 << 2 = 1100

 

*오른쪽 Shift연산(>>) : 오른쪽으로 bit를 옮긴다. 빈자리는 0으로 채워진다.

1010>>2 = 0010

 

3.비트 연산의 응용

이러한 비트 연산을 응용하여 집합의 구현에 이용할 수 있다.

우선 어떠한 정수 n이 존재할 때, (1<<n)의 연산의 결과는 n번비트가 1이 됨을 알아두자

(오른쪽 끝부터 0번비트라 하겠다.)

ex) 00000001<<3 = 00001000

집합 s가 존재한다고 할때, 비트 연산을 응용하여 다음과 같은 작업을 수행할 수 있다.

s = 0b1010

 

1. 원소 추가

s = s | (1<<n)

n번비트를 1로 만든 후, 기존의 집합과 OR연산을 통해 추가한다.

(기존의 집합에 n번비트를 1로 바꾸어준다. 원래 1이었어도 무관하다.)

 

2. 원소 제거

s = s & ~(1<<n)

~(1<<n)의 경우, n번비트만 0이고 나머지는 모두 1인 상태이다.

기존의 집합과 AND 연산을 하게 되면 n번비트가 0이므로 기존의 집합이 무엇이든간에 0이 되고, 나머지 비트의 경우 1과 AND 연산을 하기 때문에 기존 집합의 비트가 유지된다.

 

3. 원소 조회

s & (1<<n)

n번 비트가 s에 존재하는지 확인한다.

결과값이 0일 경우 해당하는 원소가 존재하지 않는 것이고, 그 외의 값이 나올 경우 존재함을 의미한다.

 

4. 원소 토글

s = s ^ (1<<n)

XOR연산을 이용해 기존의 집합에 n번 비트가 존재한다면(1일 경우) 0으로 바꿔주고, 존재하지 않다면(0일 경우) 1로 바꿔준다.

 

5. 원소 비우기

s = 0

 

6. 원소 채우기

만약 20개의 원소를 채우는 경우라면, 다음과 같은 연산을 통해 20개의 비트를 1로 채울 수 있다.

s = (1<<21) - 1