[알고리즘] 비트마스크 (Bitmask)

 

안녕하세요. 오늘은 정수의 이진수표현을 활용하여 문제를 해결하는 기법인 비트마스크에 대해 알아보겠습니다. 또한 기본적인 비트 연산자에 대해서도 설명해보려고 합니다.
비트마스크를 설명하기 전에 기본적인 비트 연산자에 대해 설명하도록 하겠습니다.

 

 

 

 

 

비트 연산자 (&, |, ^, <<, >>)

1. and 연산자 ( & )

두 수를 이진수로 표현한 뒤, and 연산을 수행합니다.

           101     (5)
           110     (6)
and  ----------
           100     (4)

2. or 연산자 ( | )

두 수를 이진수로 표현한 뒤, or 연산을 수행합니다.

           101     (5)
           011     (3)
or   ----------
           111     (7)

3. xor 연산자 ( ^ )

두 수를 이진수로 표현한 뒤, xor 연산을 수행합니다.

두 비트가 같은 값이라면 0이 되고, 다른 값이라면 1이 됩니다. 1 ^ 1 의 결과는 0인 것이 헷갈릴 수 있으니 유의해야 합니다!

a	b	a ^ b
0	0	0
1	0	1
0	1	1
1	1	0

           101     (5)
           011     (3)
xor  ----------
           110     (6)

4. left shift 연산자 ( << )

두 수를 이진수로 표현한 뒤, left shift 연산을 수행합니다.

5      = 0000101   (5)
5 << 1 = 0001010   (10)
5 << 2 = 0010100   (20)
5 << 3 = 0101000   (40)

5. right shift 연산자 ( >> )

두 수를 이진수로 표현한 뒤, right shift 연산을 수행합니다.

13      = 0001101   (13)
13 >> 1 = 0000110   (6)
13 >> 2 = 0000011   (3)
13 >> 3 = 0000001   (1)

비트마스크란 ?

정수를 이진수로 표현하여 각 비트의 상태를 활용해 데이터를 효율적으로 저장하고 연산하는 기법입니다.

예를 들어, 0~31의 수의 존재 여부를 표현해야하는 문제에 적합합니다. 이는 해당 자리의 비트를 0 또는 1로 나타내어 해결할 수 있기 때문입니다. 비트마스크를 이용해 할 수 있는 연산에는 크게 4가지가 있습니다. 수의 존재여부 확인, 추가, 삭제, 모든 수를 한번에 채우기 가 가능합니다.

 

수의 존재 여부 확인 - (s>>x)&1

x가 존재하는지 확인하려면, x번째 비트가(Zero-Based-Indexing) 1인지 확인하면 됩니다.

예를 들어, 4가 존재하는지 확인하는 과정으로 설명하겠습니다.

우선 4번째 비트가 제일 끝에 올 수 있도록 비트를 오른쪽으로 4칸 미룹니다.

그리고 마지막 비트가 1인지 0인지 확인힙니다. 이는 1과 and 연산을 통해 구할 수 있습니다.(1 = 0000001)

<4번째 비트가 1인지 판단하는 경우>
s              00000000000000000000000000100011 (35)
s >> 2         00000000000000000000000000001000 (8)
1              00000000000000000000000000000001 (1)
(s >> x) & 1   00000000000000000000000000000000 (0)