[Skill] BitMask

비트마스크란 무엇인가? 

먼저 비트는 이진수를 말하는 것인데, 비트를 활용한 테크닉을 말한다.

비트는 0과 1의 값을 가지고 있고, 문제 풀이를 할 때 보통 true/false | on/off | having/not having 으로 두고 푼다.

비트마스크를 왜 써야할까?

비트마스크를 쓰면 우리에게 이점이 무엇인지 생각을 해보자.

예를 들어보자.

우리는 배열이 3인 집합 { 1 , 2 , 3 } 가 있다고 가정한다. 여기서 몇가지의 요소를 뽑아 어떤 요소를 선택했는지 표현 할 수 있다. 즉, 집합의 어떤 요소를 구성하고 있는지를 나타내는 부분집합을 어떻게 표현할 수 있는가?

{ { 1 } { 1 , 2 } { 1 , 3 } { 2 } ... }

위와 같은 형태로 이것을 boolean 1차원 배열로 표현 할 수도 있다.

boolean[] array1 = [true,false,false] // { 1 }
boolean[] array2 = [true,true,false] // { 1, 2 }
boolean[] array3 = [true,true,true] // { 1, 2,3 }
boolean[] array4 = [false,true,false] // { 2 }

 

하지만 메모리적으로 낭비라는 생각이 든다.

그래서 이것을 우리는 비트로 표현 할 수 있다.

1<<0  =  001  = { 1 }
1<<0 | 1<<1  =  011  = { 1,2 }
1<<0 | 1<<1 | 1<<2  =  111  = { 1,2,3 }
1<<1  =  010  = { 2 }

 

즉 7이라는 정수는 부분집합 { 1, 2, 3 } 이라는 것을 뜻 할 수 있다. == Integer하나로 제어를 할 수 있다.

또한 { 1, 2 } 부분집합에서 i를 추가하고 싶으면, 단순히 i번째 비트의 값을 1로 변경해주면 된다.

이러한 삽입, 삭제, 조회와 같은 행위는 비트 연산을 통해 쉽게 제어할 수 있다.

 

AND 연산(&)

대응하는 두 비트가 모두 1일 때, 1을 반환.

 

1010 & 1111 = 1010

 

OR 연산(|)

대응하는 두 비트가 모두 1 또는 하나라도 1일 때, 1을 반환.

 

1010 | 1111 = 1111

 

XOR 연산(^)

대응하는 두 비트가 서로 다르면 1을 반환.

 

1010 | 1111 = 0101

 

NOT 연산(~)

비트의 값을 반전하여 반환.

 

~1010 = 0101

 

시프트(Shift) 연산(>>, <<)

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

 

00001010 << 2 = 101000
00001010 >> 2 = 000010 

 

출처: https://mygumi.tistory.com/361 [마이구미의 HelloWorld]