[Java/Java SE, EE] 비트 마스크(Bitmask)

비트(Bit)

비트는 이진 숫자(Binary digit)를 의미하는 데이터의 최소 단위입니다. 하나의 비트는 0 또는 1의 값 둘 중 하나만을 갖을 수 있습니다. 이는 컴퓨터에서는 true 또는 false의 의미로 사용 될 수 있고, 논리적으로는 on 또는 off의 의미로도 사용됩니다. 각 비트는 최소한의 정보만 포함하지만, 여러 개의 비트를 사용하면 정수를 표현 할 수 있습니다.

정수에서 각 비트는 자리수에 따라서 2^n의 크기를 갖고, 가장 낮은 자리수(최하위 비트)는 2^0부터 시작합니다. 각 비트는 상위 비트로 이동 할 수록 n의 값이 1씩 증가합니다. 아래 표는 각 정수를 구성하는 비트의 모음입니다. 예를 들어 정수 3은 (2^1+2^0)의 비트로 표시 할  수 있습니다.

정수	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
1	0	0	0	0	0	0	0	1
2	0	0	0	0	0	0	1	0
3	0	0	0	0	0	0	1	1
4	0	0	0	0	0	1	0	0
5	0	0	0	0	0	1	0	1
6	0	0	0	0	0	1	1	0
7	0	0	0	0	0	1	1	1
8	0	0	0	0	1	0	0	0
9	0	0	0	0	1	0	0	1
10	0	0	0	0	1	0	1	0

비트 마스크(Bitmask)란?

비트 마스크는 정수의 이진 표현법을 이용하여 알고리즘, 자료구조를 구현하는 기법입니다. 이를 위해 비트 논리 연산자(NOT, AND, OR, XOR)과 비트 시프트 연산자(<<, >>, >>>)를 사용합니다.

구분	연산자	항의 개수	연산식 결과
비트 논리	~	단항	비트 부정(NOT), 비트 값(0 또는 1)을 상호 반전
비트 논리	&	이항	비트 곱(AND), 두 피연산자의 각 비트 자릿수 별로 모두 1인 경우 1, 그렇지 않은 경우 0
비트 논리	|	이항	비트 합(OR), 두 피연산자의 각 비트 자릿수 별로 하나라도 1인 경우 1, 모두 0인 경우 0
비트 논리	^	이항	비트 배타적 논리 합(XOR), 두 피연산자의 각 비트 자릿수 별로 서로 다르면 1, 같으면 0
비트 시프트	<<	이항	피연산자의 비트를 좌측으로 다른 피연산자 만큼 이동
비트 시프트	>>	이항	피연산자의 비트를 우측으로 다른 피연산자 만큼 이동
비트 시프트	>>>	이항	피연산자의 비트를 우측으로 다른 피연산자 만큼 이동

비트 마스크는 보통 집합에 대한 알고리즘과 자료구조를 구현하기 위해 사용됩니다. 비트 마스크 기법을 사용하지 않으면, 집합을 표현하는 가장 단순한 자료구조는 아래와 같이 배열을 사용할 수 있습니다. 실제 메모리 구조와는 다르지만, on 또는 off의 상태를 원소에 대한 집합을 표현한다고 했을 때 5개의 원소를 사용하면 5바이트가 소모됩니다.

boolean[] m = new boolean[] { false, false, false, false, true};

하지만 비트 마스크를 사용하면 정수 하나를 사용하여 32개(4Byte=8Bit*4=32Bit)의 원소를 표현 할 수 있습니다. 원소가 on 또는 off 하는 속성은 비트의 속성과 일치하기 때문입니다. 하나의 비트가 하나의 원소에 대응하며, N개의 원소를 표현하는 집합을 구성하기 위해서 N개의 비트만 소모하면 됩니다.

int m = 1;	// 2진수 0000 0001 == false false false false true

이러한 특성과 관련해 비트 마스크를 사용했을 때의 장점들은 다음과 같습니다.

• 메모리 사용량
  앞서 설명처럼 각 원소의 on 또는 off 속성을 표현하기 위한 자료구조 중 가장 적은 메모리를 사용합니다. 메모리 사용량에 대한 이점이 비트 마스크의 가장 큰 특징이자 장점입니다.
• 수행 속도
  비트 연산 대부분이 O(1)의 시간 복잡도를 갖습니다. 이는 연산의 횟수가 많아질수록 다른 연산과 비교했을 때 더 극명하게 나타납니다.
• 간결성
  아래에서 소개하겠지만, 비트 마스크를 사용한 집합을 구현할 경우 코드가 굉장히 간결해집니다. 

비트 마스크를 사용한, 공집합 생성

공집합은 집합에 원소가 하나도 없는 상태를 의미합니다. 원소가 없는 상태, 즉 비트 값 0(false, off)을 사용하여 표현하며, 모든 비트 값이 0으로 채워진 정수는 0입니다. 따라서 공집합을 생성하거나 집합을 공집합으로 초기화 하는 경우 0을 저장합니다(비트 연산자가 사용되지는 않습니다).

m = 0

예시에서는 편의상 int 데이터 타입을 사용하고 있으나, 실제로는 원소의 크기에 알맞는 데이터 타입을 사용하는 것을 권장합니다.

 

int m = 0;

System.out.println(Integer.toBinaryString(m));    // 0000 0000

비트 마스크를 사용한, 전체 집합 생성

전체 집합은 공집합의 반대 의미로 집합의 모든 원소가 포함된 상태를 의미합니다. 원소가 있는 상태, 즉 비트 값 1(true, off)를 사용하여 표현하며, 모든 비트 값이 1로 채워진 정수를 사용합니다. 

다음은 전체 집합을 생성하는 알고리즘입니다.

m = (1 << N) - 1

N은 집합을 구성하는 원소의 개수를 뜻합니다.  전체 집합의 크기가 N이므로 1 << N은 사실상 논리적인 오버플로우에 해당합니다. 집합의 크기를 넘어서는 자리수(최상위 비트 위)에 1을 마킹하고, 이 산출 값에 1을 빼서 최상위 비트부터 최하위 비트의 값을 1로 채우는 원리입니다.

int m = (1 << 8) - 1;

System.out.println(Integer.toBinaryString(m));    // 1111 1111

예시의 코드를 각 비트에 대해서 풀어서 계산하면 다음과 같습니다. 집합의 크기가 8이므로, 2^8에 해당하는 비트 자리수는 사실상 오버플로우 자리입니다.

연산식	산출 전 비트									산출 후 비트
	2^8	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0	2^8	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
1 << 8	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0
-1	1	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

비트 마스크를 사용한, 집합에 원소 추가

집합에 원소를 추가한다는 것은, 특정 자리수의 비트를 0에서 1로 바꾸는 것입니다. 원소 추가를 위한 알고리즘에는 비트 논리 합 연산자를 사용합니다. 특정 자리수에 해당하는 n에 -1을 더하는 이유는 첫 번째(n=1) 원소를 추가하기 위한 연산식을 x | 1 << 0으로 만들기 위함입니다. 원소의 인덱스를 0부터 정의하는 경우 (n - 1)대신 (n)을 사용합니다.

m = x | (1 << (n - 1))

 

아래 예시는 1111 0000 집합에서 최하위 세 번째  원소(n=3)를 추가합니다.

int x = Integer.parseInt("11110000", 2);
int n = 3;
int m = (x | (1 << (n - 1)));
		
System.out.println(Integer.toBinaryString(m));		// 11110100

비트 마스크를 사용한, 집합에서 원소 삭제

집합에서 원소를 삭제한다는 것은, 특정 자리수의 비트를 1에서 0으로 바꾸는 것입니다. 원소 추가를 위한 알고리즘에는 비트 논리 곱과 논리 부정 연산자를 사용합니다. 

m = x & ~(1 << (n - 1))

 

아래 예시는 1111 1111 전체 집합에서 최하위 세 번째 원소(n=3)를 삭제합니다.

int x = Integer.parseInt("11111111", 2);
int n = 3;
int m = (x & ~(1 << (n - 1)));

System.out.println(Integer.toBinaryString(m));    // 1111 1011

연산식 중 비트 부정 연산자(~)의 이유는 특정 원소만 0으로 마킹하고, 나머지 자리는 원래 집합(x=1111 1111)의 값을 그대로 사용하기 위함입니다. 비트 논리 곱에서 y & 1의 결과는 항상 y에 의존하는 특성을 활용한 것입니다.

연산식	산출 전 비트								산출 후 비트
	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
1 << (n - 1)	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0
~	0	0	0	0	0	1	0	0	1	1	1	1	1	0	1	1
&	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1

비트 마스크를 사용한, 집합에서 원소 탐색

특정 원소(자리수)가 집합에 포함되어 있는지 원소를 탐색합니다. 이는 원래 값에서 특정 자리수에 해당하는 비트만 추출했을 때, 값이 0이 아니라면 원소가 포함된 것이고, 값이 0인 경우 원소가 포함되지 않은 것과 같습니다.

m = (x & (1 << (n - 1))

아래 예시는 1010 1010 집합에서 최하위 세 번째 원소를 탐색합니다.

int x = Integer.parseInt("10101010", 2);
int n = 3;
int m = (x & (1 << (n - 1)));

System.out.println((0 == m) ? true : false);		// 0 == false

원소를 삭제하는 알고리즘과 유사하지만, 비트 논리 부정(~) 연산자가 제외되었습니다. 이는 논리 곱 산출 과정에서 특정 비트를 제외한 나머지 비트는 0과 논리 곱을 수행함으로써 완전히 배제하는 과정의 일환입니다. 이는 비트 논리 곱에서 y & 0의 결과는 항상 y에 관계없이 0으로 고정되는 특성을 활용한 것입니다. 반대로 탐색하려는 원소의 자리수는 1로 고정함으로써 y & 1의 결과로 해당 원소의 포함 여부를 확인합니다. 즉, 나머지 비트 자리수는 모두 0이 되고, 해당 원소의 비트만 추출하므로 원소의 포함 여부를 산출하게 됩니다.

연산식	산출 전 비트								산출 후 비트
	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
1 << (n - 1)	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0
&	1	0	1	0	1	0	1	0	0	0	0	0	0	0	0	0

비트 마스크를 사용한, 원소의 상태 토글(Toggle)

토글이란 두 가지 상태(1 또는 0, true 또는 false, on 또는 off 등) 값을 다른 상태로 바꾸는 행위입니다. 이번에는 비트 마스크를 사용하여 집합 내 특정 원소의 상태를 다른 상태로 변경하는 알고리즘에 대한 소개입니다.

m = x ^ (1 << (n - 1))

아래 예시는 1010 1010 집합에서 최하위 세 번째 원소의 상태를 연속으로 두 번 토글합니다.

int x = Integer.parseInt("10101010", 2);
int n = 3;
int m = (x ^ (1 << (n - 1)));
int z = (m ^ (1 << (n - 1)));

System.out.println(Integer.toBinaryString(m));    // 1010 1110
System.out.println(Integer.toBinaryString(z));    // 1010 1010

토글을 위해서 비트 배타적 논리 합(XOR) 연산자를 사용합니다. 배타적 논리 합은 두 피연산자의 값이 서로 다르면 1을 반환하고, 그렇지 않으면 0을 반환합니다. 배타적 논리 합이 수행되는 비트는 y  ^ 1 연산식이 고정되므로 y가 1인 경우 0, y가 0인 경우 1을 산출합니다.

연산식	산출 전 비트								산출 후 비트
	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
1 << (n - 1)	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0
^	1	0	1	0	1	0	1	0	1	0	1	0	1	1	1	0

비트 마스크를 사용한, 두 집합의 합집합

합집합은 두 집합의 원소 전체를 합친 결과입니다. 단, 동일한 원소를 포함하고 있는 경우에 대해서는 중복으로 포함하지는 않고 단일 원소로 처리합니다. 합집합의 계산을 위해서 비트 논리 합(OR) 연산자를 사용합니다. 여기서 두 개의 피연산자는 모두 집합입니다.

m = x | y

알고리즘은 단순히 비트 논리 합에 불과합니다. 비트 논리 합 그 자체가 각 비트의 합을 구하는 연산자이기 때문입니다.

int x = Integer.parseInt("10101010", 2);
int y = Integer.parseInt("00001111", 2);

System.out.println(Integer.toBinaryString(x | y));    // 1010 1111

 

비트 마스크를 사용한, 두 집합의 교집합

교집합은 두 집합의 원소 중 상호 교차되는 원소를 추린 결과입니다. 교집합의 계산을 위해서 비트 논리 곱(AND) 연산자를 사용합니다. 여기서 두 개의 피연산자는 모두 집합입니다.

m = x & y

알고리즘은 단순히 비트 논리 곱에 불과합니다.

int x = Integer.parseInt("10101010", 2);
int y = Integer.parseInt("00001111", 2);

System.out.println(Integer.toBinaryString(x & y));    // 0000 1010

비트 마스크를 사용한, 두 집합의 차집합

차집합은 하나의 집합에서 다른 집합의 원소를 모두 배제한 결과입니다. 차집합의 계산을 위해서 비트 논리 곱(AND), 비트 논리 부정(NOT) 연산자를 사용합니다. 여기서 두 개의 피연산자는 모두 집합입니다.

m = x & (~y)

알고리즘은 교집합 알고리즘의 역과 같습니다. 교집합에서는 y 집합과 교차하는 집합을 산출하지만, 차집합 연산에서는 y 집합에 대한 부정(y')을 구하여 y' 집합과 교차하는 집합을 산출하게 됩니다.

int m = Integer.parseInt("10101010", 2);
int n = Integer.parseInt("00001111", 2);

System.out.println(Integer.toBinaryString(m & (~n)));     // 1010 0000

y의 부정(y')은 y 집합이 포함하고 있는 원소를 모두 배제합니다. 즉, y' 집합과 비트 논리 곱을 수행하면 y 집합이 포함하고 있던 원소를 모두 배제하는 결과를 갖습니다.

연산식	산출 전 비트								산출 후 비트
	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
(~y)	0	0	0	0	1	1	1	1	1	1	1	1	0	0	0	0
&	1	0	1	0	1	0	1	0	1	0	1	0	0	0	0	0

비트 마스크를 사용한, 집합의 크기

집합의 크기는 자바의 내장 함수(Integer.bitCount)를 사용합니다. 이 함수는 집합(정수)에서 켜져있는 비트 개수를 반환합니다.

int m = Integer.parseInt("10101010", 2);

System.out.println(Integer.bitCount(m));      // 4

비트 마스크를 사용한, 집합의 가장 작은 자리수의 원소 탐색

집합 내에서 켜져있는 비트 중 자리수가 가장 낮은(최하위) 비트를 찾는 알고리즘입니다. 이 알고리즘은 비트 논리 곱(AND) 연산자와 2의 보수의 성질을 이용합니다.

m = x & (-x)

아래 예시는 1010 10101 집합에 대한 가장 작은 자리수의 원소를 탐색한 결과입니다.

int m = Integer.parseInt("10101010", 2);

System.out.println(Integer.toBinaryString(m & (-m)));     // 0000 0010

컴퓨터는 2의 보수를 사용하여 음수를 표현합니다. 2의 보수는 1의 보수에서 최하위 비트에 1을 더한 값입니다. 1의 보수는 각 비트에 대한 역입니다.

아래 첫 번째 행은 집합 m을 1의 보수 처리하고 있습니다. 두 번째 행은 m의 1의 보수에 대해서 최하위 비트에 1을 더한 결과입니다. 이 과정을 거치면, 2의 보수는 원래 집합 m에서 가장 작은 자리수의 원소를 켜고 나머지 원소는 토글하게 됩니다. 결국 토글 된 원소들은 비트 논리 곱 연산에 의해서 항상 0이 되고, 가장 작은 자리수의 원소만 추출됩니다.

연산식	산출 전 비트								산출 후 비트
	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
-m (1의 보수)	1	0	1	0	1	0	1	0	0	1	0	1	0	1	0	1
-m (2의 보수)	1	0	1	0	1	0	1	0	0	1	0	1	0	1	1	0
&	1	0	1	0	1	0	1	0	0	0	0	0	0	0	1	0

이 알고리즘은 펜윅 트리(Fenwick tree) 등 다른 알고리즘에서도 적용됩니다.