[Algorithm] BitMask, 비트 마스크

비트마스크란?

비트마스크는 0 또는 1로 표현되는 이진수 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 알고리즘을 말한다.

• 이진수 표현을 사용하는 것이므로 비트마스크는 알고리즘이 아니라 "기법" 정도로 보는 의견도 있다.

---

비트마스크는 왜 사용할까?

1. 빠른 수행 시간

• 비트마스크 연산은 bit 연산이기 때문에 대부분 O(1)에 구현된다.
• 연산 횟수가 늘어날수록 차이가 매우 커지게 된다.

2. 간결한 코드

• 다양한 집합 연산을 비트 연산자를 통해 한 줄로 작성할 수 있기 때문이다.

3. 적은 메모리 사용량
   Nbit 이진수 하나로 2^N가지의 경우를 표현 할 수 있기 때문에 메모리 측면에서 효율적이며 더 많은 데이터를 미리 계산해서 저장해 두어 더 나아가 DP에 유용하게 활용할 수 있다.

비트마스크 활용을 간단히 보자.

아래와 같이 단순히 배열을 통해 구현한다면 많은 메모리를 차지하고 오버헤드가 증가할 것이다.

int[] ary1 = {1, 1, 1, 1, 0};
int[] ary2 = {1, 1, 0, 1, 0};
...

하지만 각 요소를 인덱스처럼 표현하여 아래와 같이 부분집합으로 표현한다면 메모리의 부담을 줄일 수 있고 삽입, 삭제, 조회와 같은 연산도 쉽게 제어할 수 있다.

{ 0, 1, 2, 3, 4 } => 11111 => (2^4 * 1) + (2^3 * 1) + (2^2 * 1) + (2^1 * 1) + (2^0 * 1) = 31
{ 1, 2, 3, 4 } 	  => 11110 => (2^4 * 1) + (2^3 * 1) + (2^2 * 1) + (2^1 * 1) = 30 
{ 1, 2, 4 } 	  => 10110 => (2^4 * 1) + (2^2 * 1) + (2^1 * 1) = 22
{ 2, 4 } 		  => 10100 => (2^4 * 1) + (2^2 * 1) = 20
{ 1 } 			  => 00010 => (2^1 * 1) = 2

---

비트 마스크 연산

1. AND 논리 연산자 ( & )

비교하는 비트가 모두 1이면 1을 반환한다.

1001 AND 1011 = 1001

// javascript code

const a = 9;
const b = 11;

console.log(a & b); // 9

// java code

int a = 9;
int b = 11;

// 10진수
System.out.println(a & b);							// 9
// 2진수
System.out.println(Integer.toBinaryString(a & b));	// 1001

2. OR 논리 연산자 ( | )

비교하는 비트 중에서 하나라도 1이면 1을 반환한다.

1001 OR 1011 = 1011

// javascript code

const a = 9;
const b = 11;

console.log(a | b); // 11

// java code

int a = 9;
int b = 11;

// 10진수
System.out.println(a | b);							// 11
// 2진수
System.out.println(Integer.toBinaryString(a | b));	// 1011

3. XOR(베타) 논리 연산자 ( ^ )

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

1001 XOR 1011 = 0010

// javascript code

const a = 9;
const b = 11;

console.log(a ^ b); // 2

// java code

int a = 9;
int b = 11;

// 10진수
System.out.println(a ^ b);							// 2
// 2진수
System.out.println(Integer.toBinaryString(a ^ b));	// 10

4. NOT(부정) 논리 연산자 ( ~ )

피연산자가 하나뿐이며 비트의 값을 반전시킨다.

1의 보수(One's Complement) 방식으로서 비트를 반전시켜 음수를 표현한다.

NOT 1001 = 0110

// javascript code

const a = 9;

console.log(~a); // -10

// java code

int a = 9;

// 10진수
System.out.println(~9);							// -10
// 2진수
System.out.println(Integer.toBinaryString(~a));	// 11111111111111111111111111110110 

5. 왼쪽 SHIFT 연산자 ( << )

지정한 수만큼 비트 전체를 왼쪽으로 이동한다.

몇 칸 이동했는지에 따라 2의 제곱만큼 수가 곱해진다.

3 << 2
= 3 * 2^2 = 12

3(011)을 2칸 왼쪽으로 밀면 오른쪽부터 0이 2개 채워진다.
결과값은 12(01100)이 된다.

// javascript code

const a = 3;
const b = 2;

console.log(a << b); // 12

// java code

int a = 3;
int b = 2;

// 10진수
System.out.println(a << b);							// 12
// 2진수
System.out.println(Integer.toBinaryString(a << b));	// 1100

6. 오른쪽 SHIFT 연산자 ( >> )

지정한 수만큼 비트 전체를 오른쪽으로 이동한다.

오른쪽에 있는 비트가 소멸되기 때문에 규칙성이 없다.

16 >> 3
= 16 / 2^3 = 2

16(10000)을 3칸 오른쪽으로 밀면 왼쪽부터 0이 3개 채워진다.
결과값은 2(00010)이 된다.

여기서 중요한 것은 맨 앞은 동일한 부호비트로 채우되 항상 0으로 채우는 것은 아니다.
음수일 경우 1로 채워준다.

// javascript code

const a = 16;
const b = 3;

console.log(a >> b); // 2

// java code

int a = 16;
int b = 3;

// 10진수
System.out.println(a >> b);							// 2
// 2진수
System.out.println(Integer.toBinaryString(a >> b));	// 10

7. 부호 없는 오른쪽 SHIFT 연산자 ( >>> )

지정한 수만큼 32비트 숫자의 모든 비트를 오른쪽으로 이동하며 빈 비트는 전부 0으로 채운다.

양수에서는 오른쪽 시프트와 동일하게 동작하지만 음수일 경우 빈 비트를 0으로 채우기 때문에 다르게 동작한다.

즉 해당 연산은 항상 양수를 반환한다.

-16 >>> 3
= 536870910

// javascript code

const a = -16;
const b = 3;

console.log(a >>> b); // 536870910

// java code

int a = -16;
int b = 3;

// 10진수
System.out.println(a >>> b);							// 536870910
// 2진수
System.out.println(Integer.toBinaryString(a >>> b));	// 11111111111111111111111111110