비트마스크

코딩 테스트 시 필요한 이유

BitMask는 코딩 테스트에서 많이 활용되는 기법은 아니다. 만약 BitMask를 활용해야 하는 문제라면 개인적으로는 다른 문제를 푸는 게 더 효율적이라 생각할 정도로 굳이? 싶은 기법이긴 하다.

 

하지만 개념 및 사용 방법을 알지만 효율을 위해 다른 문제를 푸는 것과 아예 몰라서 다른 문제를 푸는 것은 매우 다른 상황이라고 생각하기 때문에 한 번 정리해보겠다.

---

아래에 나오는 모든 수들은 10진법이 아닌 2진법이라고 간주하고 정리하겠다.
이후 어떻게 10진법에서 BitMask 기법을 활용할 수 있는지 언급하겠다.

Shift 연산(>>, <<)

왼쪽 또는 오른쪽으로 비트를 옮긴다.

00100 << 2 // 결과 : 10000
00100 >> 2 // 결과 : 00001

 

XOR 연산(^)

대응하는 두 비트가 같으면 0, 다르면 1을 반환한다.

1010 ^ 1111 // 결과 : 0101

 

AND 연산(&)

대응하는 두 비트 모두 1일 때만 1을 반환한다.

1010 & 1111 // 결과 : 1010

 

OR 연산(|)

대응하는 두 비트 중 하나라도 1이라면 1을 반환한다.

1010 | 1111 // 결과 : 1111

 

NOT 연산(~)

비트의 값을 반전시킨다.

~1010 // 결과 : 0101

---

실제 BitMask 활용법

이진법이라면 위 예시처럼 활용하면 되겠지만 안타깝게도 우린 자바에서 10진법을 많이 활용한다.

예를 들어 "00100 << 2"를 수행하고 싶을 경우 "8<<2"를 수행하거나 "Integer.parseInt("00100", 2) << 2"처럼 귀찮은 과정을 거쳐야 하는 것이다.

 

이런 과정을 거치지 않기 위해 BitMask를 활용할 땐 꼭 "Shift 연산"과 결합하여 많이 활용한다.

 

예시 2개 정도를 보며 어떻게 Shift 연산을 통해 BitMask 기법을 활용하는지 확인해 보자.

◎ "00000" 이진법에서 "01000"으로 값을 바꾸기

0 | (1 << 4)

 

◎ "01001" 이진법에서 "00011"으로 값을 바꾸기

int origin = 9; // 01001
(origin >> 2) | 1 // (origin >> 2) | 1 -> (00010) | 1 -> 00011

 

추가로 BitMask는 주로 배열 Index로 쓰는 경우가 많아서 만약 16Bit를 넘어갈 경우 다른 방법을 생각해보는 것도 좋다.