비트마스크

비트마스크란?

알고리즘보다는 테크닉 중 하나로써, 정수의 이진수 표현을 활용한 기법이다.
하나의 비트는 0 이나 1로 표현될 수 있습니다. 정수의 이진수 표현을 자료구조로 쓰는 기법을 말합니다.

• 용어 그대로 비트(Bit) 에 관련된 것이다.
• 비트는 이진 숫자(binary digit) 를 뜻하는 말로 컴퓨터에서 사용되는 데이터의 최소 단위이다.
• 비트는 0, 1 의 값을 가질 수 있고, true/false 또는 on/off 라는 상태를 나타낸다.
• 이건 흔히 알고 있는 지식으로 컴퓨터는 0, 1 두가지 숫자만으로 표현하는 이진법을 사용하는 것을 의미한다.

• 일반적으로 우리가 다루는 표현 방식이 0 ~ 9 숫자를 사용하는 10진법이다.
  

설명

비트마스크에서 중요한 두 가지 정보
1. 이진수는 0, 1 만을 가지고, true/false 상태를 가진다.
2. 이진수는 십진수로 표현 가능하다.

• 그렇다면 과연 이를 어떻게 활용할 수 있을까?

• 우리는 길이가 5인 집합 { 0, 1, 2, 3, 4 } 가 존재한다고 가정해본다.

• 여기서 몇가지 요소를 뽑아 어떤 요소를 선택했는 지 표현할 수 있다.

• 즉, 집합의 어떤 요소를 구성하고 있는지를 나타내는 부분집합을 어떻게 표현할 수 있는가?

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

Boolean 형태

array1 = [1, 1, 1, 1, 0];
array2 = [1, 1, 0, 1, 0];
array3 = [1, 0, 1, 0, 0];

2진수를 10진수로 표현

{ 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

• { 2, 4 } 부분집합에서 i를 추가하고 싶으면, 단순히 i번째 비트의 값을 1로 변경해주면 된다.
• 이러한 삽입, 삭제, 조회와 같은 행위는 비트 연산을 통해 쉽게 제어할 수 있다.

AND, OR, XOR, NOT, SHIFT

1. AND 연산(&)

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

1010 & 1111 = 1010

2. OR 연산(|)

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

1010 | 1111 = 1111

3. XOR 연산(^)

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

1010 | 1111 = 0101

4. NOT 연산(~)

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

~1010 = 0101

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

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

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

• 왼쪽 시프트는 A * 2^B 를 의미하고, 오른쪽 시프트는 A / 2^B 를 의미한다.
  • 0001 -> 0010 -> 0100 -> 1000 => 1, 2, 4, 8 .....
  • 1000 -> 0100 -> 0010 -> 0001 => 8, 4, 2, 1 .....
  • (A + B) / 2 를 (A + B) >> 1 로 사용할 수도 있듯이 많은 곳에서 일반적인 사칙연산을 더 효율적으로 할 수 있다.