비트 마스크(Bit Mask) 기법은 말 그대로 비트(Bit)를 마스킹하는 기술 입니다. 비트를 마스킹 한다는 것은 &(AND 연산자), | (OR 연산자) 등의 비트 연산을 활용하여 정수의 이진 비트를 처리하는 작업이라고 이해하 실 수 있습니다. 비트 마스크 기법은 항상 사용할 수 있는 것은 아니지만 특정한 경우에 사용하면 매우 효율적 일 수 있습니다. 비트 마스크의 대표적인 장점을 소개하면 다음과 같습니다.
1. 메모리를 적게 사용할 수 있습니다.
2. 프로그램이 더욱 빠르게 동작 합니다.
3. 소스코드가 직관적으로 변경 됩니다.
일반적으로 정수 7이 있을 때 이것을 비트 형태로 표현하면 다음과 같습니다.
7 : 0000000 0000000 0000000 00000111 (2진수 비트, 32bit)
위와 같이 32개의 비트로 구성되게 됩니다. 이렇게 비트 형태로 특정한 변수를 직접적으로 다루면 효과적인 경우로는 무엇이 있을까요? 대표적인 예제로는 '출석 체크'가 있습니다. 학생이 32명이라고 가정 했을 때 각각 0번부터 31번까지 번호를 붙여봅시다. 이 떄 출석을 한 학생은 1로 표현하고, 출석을 하지 않은 학생은 0으로 표현할 수 있습니다. 예시로 5번, 7번 학생만 출석을 한 경우는 다음과 같습니다.
5번, 7번만 출석 : 0000000 0000000 0000000 01010000
다시 말해, 비트 마스크 기법을 이용하면 정수 하나만 이용해서 배열을 사용한 것과 같은 효과를 낼 수 있습니다.
이제 부터 실질적으로 비트 마스크 연산 문법을 알아보도록 합시다.
1. 2진수 형태로 출력하기
int(32비트)를 기준으로 보았을 때, 가장 왼쪽 비트부터 오른쪽 비트까지 하나씩 순회하면서 각 원소를 가지고 있는지 & 연산으로 확인하여 1 혹은 0 을 출력하면 됩니다.
// 2진수 형태로 출력하기
void show() {
for (int i = 32; i > 0; i--) {
if ((num & (1 << i - 1)) > 0)
System.out.print("1");
else
System.out.print("0");
}
}
2. 모든 원소를 삭제하기
모든 원소를 삭제하고자 할 때는 단순히 변수를 0으로 초기화하면 됩니다. 기본적으로 컴퓨터는 2의 보수 체계를 가지고 있기 때문에 0으로 초기화하면 모든 비트가 0이 됩니다.
// 모든 원소를 삭제하기
void init() {
num = 0;
}
3. 모든 원소를 포함시키기
모든 원소를 포함시키고자 할 때는 변수에 -1을 넣으면 됩니다. 컴퓨터는 2의 보수 체계를 가지고 있기 때문에 -1로 초기화하면 모든 비트가 1이 됩니다.
1 : 0000000 0000000 0000000 0000001
1의 1의 보수 : 11111111 11111111 11111111 11111110
1의 2의 보수 : 11111111 11111111 11111111 11111111
따라서 -1을 넣어주면 모든 값을 포함시켜주게 됩니다.
// 모든 원소를 포함시키기
void full() {
num = -1;
}
4. 특정 원소 삭제하기
특정 원소를 삭제할 때는 (1 << i)에 NOT(~) 연산을 적용하여 변수 num와 AND(&) 연산을 수행하면 됩니다.
~(1 << i)는 특정 위치의 비트만 0이고 나머지는 전부 1이기 때문입니다.
(1 << 32) : 10000000 00000000 00000000 00000000
(1 << 31) : 01000000 00000000 00000000 00000000
~(1 << 32) : 01111111 11111111 11111111 11111111
~(1 << 31) : 10111111 11111111 11111111 11111111
이기 때문에 num 과 AND연산(&)을 수행하면 특정 원소만 0을 포함 시킵니다.
// 특정 원소를 삭제하기
void drop(int i) {
num &= ~(1<<i);
}
5. 특정 원소 포함시키기
특정 원소를 포함시킬 때는 (1 << i)를 변수 a와 OR연산( | )을 수행하면 됩니다.
(1 << 32) : 10000000 00000000 00000000 00000000
(1 << 31) : 01000000 00000000 00000000 00000000
이기 때문에 num과 OR연산( | )를 수행하면 특정 원소가 항상 1을 갖습니다.
// 특정 원소를 포함시키기
void set(int i) {
num |= (1<<i);
}
6. 특정 원소 포함 여부 확인하기
특정 원소의 포함 여부를 확인할 때는 (1<<i)을 하여 특정 비트가 1이 되도록 하고 이를 num과 AND연산(&)을 수행하면 됩니다.
// 특정 원소의 포함 여부를 확인하기
boolean isSet(int i) {
return (num & (1 << i)) > 1;
}
7. 특정 원소를 토글하기
특정 원소를 토글하고자 할 때는 (1<<i)를 하여 특정 비트가 1이 되도록 하고 이를 num과 XOR(^) 연산을 수행하면 됩니다. 결과적으로 특정 비트가 1이면 0으로 바뀌고, 0이면 1로 바뀌게 됩니다.
XOR 연산자는 두 비트가 다르면 1, 같으면 0 이기 때문에, 특정 비트가 1이면 0으로 바뀌고, 0이면 1로 바뀌게 됩니다.
(1 << 5) : 01000000 00000000 00000000 00100000
(num) : 01000000 00000000 00000000 00000000
-----------------------------------XOR연산------------------------
(결과) : 01000000 00000000 00000000 00100000
// 특정 원소 토글하기
void toggle(int i) {
num ^= (1<<i);
}
8. 마지막 원소 구하기
컴퓨터는 내부적으로 2의 보수 체계를 사용하므로 -num은 num의 대한 1의 보수에서 1을 더한 값과 동일 합니다.
그러므로 num과 -num을 AND연산(&)하면 가장 작은 비트인 마지막 원소를 구할 수 있습니다. 이때 마지막 원소는 정수형으로 반환되어 오른쪽에서 3번째 원소라면 2^(3-1) = 4가 됩니다.
7 : 00000000 00000000 00000000 00000111
-7 : 11111111 11111111 11111111 11111001
-----------------------------AND연산-------------------------
00000000 00000000 00000000 00000001 = 1
// 마지막 원소 구하기
int getLast() {
return num & -num;
}
9. 마지막 원소 삭제하기
마지막 원소를 삭제하기 위해서는 num을 (num - 1)과 AND연산(&)을 하면 됩니다. 왜냐하면 num - 1은 num의 가장 마지막 비트를 0으로 바꾸고 그보다 작은 비트들을 모두 0으로 바꾸기 때문 입니다.
7 : 00000000 00000000 00000000 00000111
7 - 1 : 00000000 00000000 00000000 00000110
-----------------------------AND연산-------------------------
00000000 00000000 00000000 00000110
// 마지막 원소 삭제하기
void dropLast() {
num &= (num - 1);
}
10. 전체 소스 코드
package idea;
public class BitMask {
public static void main(String[] args) {
BitMaskSolution bitmask = new BitMaskSolution(0);
bitmask.init();
System.out.print("모든 원소 삭제: ");
bitmask.show();
System.out.println();
bitmask.full();
System.out.print("모든 원소 포함: ");
bitmask.show();
System.out.println();
bitmask.drop(5);
System.out.print("5번째 인덱스 삭제: ");
bitmask.show();
System.out.println();
bitmask.set(5);
System.out.print("5번째 인덱스 포함: ");
bitmask.show();
System.out.println();
System.out.printf("5번째 인덱스 포함 여부: %b", bitmask.isSet(5));
System.out.println();
bitmask.toggle(5);
System.out.print("5번째 인덱스 토글: ");
bitmask.show();
System.out.println();
System.out.printf("5번째 인덱스 포함 여부: %b", bitmask.isSet(5));
System.out.println();
bitmask.dropLast();
bitmask.dropLast();
bitmask.dropLast();
System.out.print("마지막 원소 3개 삭제: ");
bitmask.show();
System.out.println();
System.out.printf("마지막 원소 구하기: %d", bitmask.getLast());
System.out.println();
}
static class BitMaskSolution {
private int num;
BitMaskSolution(int num) {
this.num = num;
}
// 2진수 형태로 출력하기
void show() {
for (int i = 32; i > 0; i--) {
if ((num & (1 << i - 1)) > 0)
System.out.print("1");
else
System.out.print("0");
}
}
// 모든 원소를 삭제하기
void init() {
num = 0;
}
// 모든 원소를 포함시키기
void full() {
num = -1;
}
// 특정 원소를 삭제하기
void drop(int i) {
num &= ~(1<<i);
}
// 특정 원소를 포함시키기
void set(int i) {
num |= (1<<i);
}
// 특정 원소 토글하기
void toggle(int i) {
num ^= (1<<i);
}
// 특정 원소의 포함 여부를 확인하기
boolean isSet(int i) {
return (num & (1 << i)) > 1;
}
// 마지막 원소 구하기
int getLast() {
return num & -num;
}
// 마지막 원소 삭제하기
void dropLast() {
num &= (num - 1);
}
}
}
'Algorithm' 카테고리의 다른 글
| DFS (깊이 우선 탐색) (0) | 2021.03.02 |
|---|---|
| Heap Sort (힙정렬) (0) | 2021.02.16 |
| KMP 문자열 매칭 알고리즘 (0) | 2021.01.29 |
| N Queens 문제 (체스 여왕 문제) (0) | 2021.01.27 |
| 경우의수를 비트마스크로 표현하는 법 (0) | 2021.01.23 |