[알고리즘 이론] 8. 비트마스킹

비트 마스크

• 알고리즘이 아닌 하나의 기법이다.
• 정수를 이진수로 표현하고, 비트 연산으로 다양한 문제를 해결해나가는 방법이다.

예시

• 열쇠가 a, b, c, d, e, f로 6개가 있다고 가정하고, 가지고 있는 열쇠가 a, c, e 일 때

// 가지고 있는 열쇠를 1, 아닌 것을 0으로 표시한다.
// -> 열쇠말고 다양한 곳에서 사용 가능하다. 
// 1 (true), 0 (false) 로도 가능
a b c d e f
1 0 1 0 1 0 

비트 연산자

1. AND

// & : 대응되는 비트가 모두 1이면 1을 반환한다.
00001111 & 00010101 = 00000101

2. OR

// | : 대응되는 비트 중에서 하나라도 1이면 1을 반환한다.
00001111 | 00010101 = 00011111

3. XOR

// ^ : 대응되는 비트가 서로 다르면 1을 반환한다.
00001111 ^ 0001010101 = 00011010

4. NOT

// ~ : 비트를 1이면 0으로, 0이면 1로 반전시킨다.
~00001111 = 11110000

5. 시프트 연산자

<< : 지정한 수만큼 비트들을 전부 왼쪽으로 이동 -> 이동되고 남은 비트는 0으로 채움
>> : 부호를 유지(이동되고 남은 비트는 부호 비트로 채움)하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴

00001010<<2 = 101000 (곱하기 2)
00001010>>@ = 000010 (나누기 2)

알고리즘 문제 추천

1. 부분수열의 합 (실버 2)

• https://www.acmicpc.net/problem/1182

2. 달이 차오른다, 가자 (골드 1)

• https://www.acmicpc.net/problem/1194

참고 자료

https://hailey-v.tistory.com/23