[JAVA] 비트마스크(Bit Mask)란?

- 비트마스크(Bit mask)란?

 

비트마스크란 비트(bit) 단위로 데이터를 조작하고 검사하는 방법입니다. 주로 특정 비트 위치에 Flag를 설정하거나 상태를 나타내는데 사용되며, 이러한 Flag를 검사하여 코드 동작을 제어하거나 데이터를 표현할 수 있습니다. 비트 마스크는 비트 단위 연산을 사용하여 만들거나 조작할 수 있습니다. 

 

비트마스크의 장점은 아래와 같습니다. 

• 비트 연산인 만큼 메모리를 효율적으로 사용 가능하며 수행 시간이 빠릅니다.
• Dynamic Programming이나 순열 등 일반적인 배열만으로 해결하기 어려운 문제에 유용합니다.
• 집합을 배열의 인덱스로 표현이 가능합니다. 

각 비트는 집합의 요소를 나타내며, 해당 비트가 1이면 해당 요소가 집합에 속하는 것으로 간주됩니다. 비트 마스크는 주로 작은 메모리 공간과 빠른 수행 시간을 요구하는 문제에서 유용하게 사용되며, 특히 집합과 같은 문제를 해결하는 데 도움이 됩니다. 

 

 

- 비트마스크(Bit mask) 예시

 

위에서 언급했지만, 비트마스크는 이진수를 이용하여 1(true) 또는 0(false)의 정보를 나타냅니다.

 

예를 들어, 스위치가 4개가 있고 각 스위치의 상태(켜짐 또는 꺼짐)를 나타내려 하는 상황입니다. 이때 0을 꺼진 상태, 1을 켜진 상태로 설정하여 각 스위치 상태를 비트로 표현할 수 있습니다.

스위치 1 : 0001, 스위치 2 : 0010, 스위치 3 : 0100, 스위치 4 : 1000
비트 마스크 : 0101  //스위치 1과 3이 켜짐

 

다른 예로 배열 [1, 2, 3, 4]가 있을 때 비트마스킹을 통해 배열의 각 요소를 비트 단위로 표현할 수 있습니다.

[1, 2, 3, 4] → 1111
[2, 3] → 0110

 

 

- 비트 연산자

 

비트 연산자는 비트 단위에서 논리 연산을 할 때 사용하는 연산자로, 아래는 일반적으로 사용되는 비트 연산자입니다.

 

1. AND (&)

두 비트가 모두 1일 경우 1을 반환합니다.

int a = 12;  //1100
int b = 6;  //0110
int result = a & b;  //결과 : 0100 (10진수로 4)

 

2. OR (|)

두 비트 중 하나 이상이 1일 경우 1을 반환합니다.

int a = 12;  //1100
int b = 6;  //0110
int result = a | b;  //결과 : 1110 (10진수로 14)

 

3. XOR (^)

두 비트가 서로 다를 경우 1을 반환합니다.

int a = 12;  //1100
int b = 6;  //0110
int result = a & b;  //결과 : 1010 (10진수로 10)

 

4. NOT (~)

0은 1로, 1은 0으로 변환합니다.

int a = 12;  //1100
int result = ~a;  //결과 : 0011 (10진수로 -13)

 

5. LEFT SHIFT (<<)

비트를 왼쪽으로 이동시키며, 이동된 비트는 0으로 채워집니다.

int a = 12;  //1100
int result = a << 2;  //결과 : 110000 (10진수로 48)

 

6. RIGHT SHIFT (>>)

비트를 오른쪽으로 이동시키며, 이동된 비트는 부호에 따라 0 또는 1로 채워집니다.

int a = 12;  //1100
int result = a >> 2;  //결과 : 0011 (10진수로 3)

 

 

- 배열 요소 조회 & 삽입 & 삭제하기

 

1. 조회하기

비트 연산을 사용하여 이진수 n의 i번재 비트 값이 1인지 혹은 0인지를 확인해봅시다.

 

먼저, 1 << i 연산을 통해 i번째 비트만 1이고 나머지 비트는 0인 비트마스크를 만듭니다. 

이후 n과 AND 연산을 수행합니다. 즉 정리하면 n & (1 << i) 연산을 수행합니다.

 

위 결과값이 0이라면, n의 i번째 비트는 0입니다. 왜냐하면 n과 i번째 비트만 1인 비트마스크를 AND 연산했을 때 0이라면 n에서 i번째 비트가 0이여야 하기 때문입니다. 

1000(8) & 0100(1 << 2) → 0000

 

반대로, 위 결과값이 0보다 크다면 n의 i번째 비트는 1입니다. 

1100(12) & 0100(1 << 2) → 0100

 

2. 삽입하기

이진수 n의 i번째 비트 값을 1로 변경해봅시다. 이때는 n | (1 << i) 연산을 수행하여, 두 비트 중 한 비트가 1이면 1을 반환하는 OR(|) 연산자의 속성을 이용하면 됩니다.

 

위에서 예시를 들었던 '1000(8) & 0100(1 << 2) → 0000'을 보면 2번째 비트가 0이란 것을 알게 되었습니다.

여기서 8의 2번째 비트를 1로 변경하기 위해 8과 1 << 2를 OR 연산하면 아래와 같이 1로 변경됩니다.

1000(8) | 0100(1 << 2) → 1100

 

3. 삭제하기

마지막으로 이진수 n의 i번째 비트 값을 0으로 변경하여 요소를 삭제해봅시다. 위의 예시에서 2번째 비트를 1로 바꾸었던 걸 다시 0으로 바꾸어야 하는데, 그럴려면 1과 0을 AND 해주면 됩니다. 그렇다면 n의 i번째 비트는 1인 상태에서 1 << i에 NOT을 취해주면 i번째 비트만 0이 되고 나머지는 모두 1인 비트마스크를 생성합니다. 이제 생성한 비트마스크 ~(1 << i)을 n과 AND 해주면 해당 비트를 0으로 변경할 수 있습니다. 즉, n & ~(1 << i) 연산을 수행해주면 됩니다.

1100(12) & 1011(~(1 << 2)) → 1000(8)