비트마스크(BitMask)에 대해서 알아보자

비트마스크에 대해서 본격적으로 알아보기 전, 먼저 비트연산에 대해서 알아보도록 하자

 

비트 연산이란?

비트 연산이란 한 개 또는 두 개의 이진수에 대해서 비트 단위로 수행하는 연산을 말한다.

비트 연산의 종류로는 AND, OR, NOT, XOR, 쉬프트 연산이 있다.

 

• AND(&)

두 이진수의 각 자릿수를 비교해 두 값이 모두 1일때만 1을, 나머지의 경우에는 0을 계산한다.

0111 & 1101 = 0101

• OR(|)

두 이진수의 각 자릿수를 비교해 두 값이 모두 0일때만 0을, 나머지의 경우에는 1을 계산한다.

0111 | 1101 = 1111

• NOT(~)

이진수의 각 자릿수의 값을 반대로 바꾸는 연산이다. 0일 경우 1로, 1일 경우 0으로 바꿔준다.

~0111 = 1000

• XOR(^)

두 이진수의 각 자릿수를 비교해, 두 값이 같을 경우 0 다를 경우 1을 계산한다.

0111 ^ 1101 = 1010

 

 

그냥 숫자를 가지고도 비트 연산을 할 수 있는데, 만약 A=13, B=57의 두 수에 대해서 AND연산과 OR연산을 수행해보자.

숫자를 가지고 비트연산을 하는 경우에는 먼저 숫자를 이진수로 치환해준 뒤에 각 자릿수별로 비트 연산을 수행하면 된다.

A=13, B=57에 대해서 각 연산을 수행한 결과는 다음과 같다.

 

 

		int a = 13;
		int b = 57;

		System.out.println("A = " + Integer.toBinaryString(a));
		System.out.println("B = " + Integer.toBinaryString(b));

		System.out.println("A&B = " + Integer.toBinaryString(a & b) + " = " + (a & b));
		System.out.println("A|B = " + Integer.toBinaryString(a | b) + " = " + (a | b));
		System.out.println("A^B = " + Integer.toBinaryString(a ^ b) + " = " + (a ^ b));

 

NOT연산의 경우는 자료형에 따라서 결과가 달라지는데,

int의 경우 4byte, 즉 32bit 자료형이기 때문에 1101을 not연산하면 생략되었던 앞의 27자리까지 NOT연산이 이루어져서 11111111111111111111111111110010라는 결과가 나오게 된다.

즉 자료형의 크기에 따라서 달라진다고 보면 되시겠다.

 

 

쉬프트 연산

쉬프트 연산 또한 비트 연산의 한 종류로, 말그대로 비트를 shift, 밀어버리는 연산을 뜻한다.

shift left(<<)와 shift right(>>)로 두 종류의 연산이 있다.

A>>B연산을 할 경우에 A를 오른쪽으로 B비트만큼 민다는 의미이다.

 

• shift left(<<)

비트를 왼쪽으로 미는 연산이다. 비트를 밀면서 새로 생긴 곳에는 0으로 채워준다.

예를들어 13을 예시로 들어보자.

13 << 2 연산을 수행한다고 했을 때,

1101(2) << 2 = 110100(2) = 52

 

여기서 한 가지 사실!! 비트의 자릿수는 각 2^n을 나타내기 때문에, 맨 끝에 두 개의 비트가 추가된다는 사실은 비트의 자릿수마다 2^2이 곱해진다는 사실!!!

그러면 맨 끝에 B개의 비트를 추가하면 2^B를 곱하면 된다!!

즉, A<<B의 십진수 결과로는 A*2^B가 나오게 된다!!!

 

• shift right(>>)

비트를 오른쪽으로 미는 연산이다. 밀린 비트는 사라지게 된다.

역시 13을 예시로 들었을 때

13 >> 2 연산을 해보자.

1101(2) >> 2 = 11(2) = 3

 

shift left연산때와 같은 맥락으로, 비트 두 개를 지우면 각 자릿수는 2^2만큼 나눠지게 된다.

그러면 B개의 비트를 없앤다면 각 비트 자릿수마다 2^B만큼 숫자가 작아지게 될 것이다.

즉, A>>B의 십진수 결과로는 A/2^B가 나오게 된다!!!

 

 

비트 마스크란?

이제 본격적으로 비트 마스킹에 대해서 알아보도록 하겠다.

비크 마스크란 비트의 성질(0과 1의 값만 가짐)을 이용하여 이를 true/false의 상태로 나타내서 수의 집합을 나타내는 방법이다.

예를 들어 0~9까지의 수 중 랜덤하게 4개를 뽑을건데, 그 집합이 {2, 4, 5, 9}라고 해보자.

그러면 단순히 숫자 4개의 배열을 만들어서 {2, 4, 5, 9}를 저장해주는 것이 아니라, 10자리의 비트를 이용하여

1000110100라고 표현해주는 것이다.

 

활용할 때는 {2, 4, 5, 9}의 정수 네개짜리 배열을 사용하는 것보다 당연히 1000110100= 564, 정수 하나를 사용하는 것이 이득

 

보통 0부터 N-1까지 정수로 이루어진 집합을 나타낼 때 사용한다.

 

그러면 비트마스크를 활용하는 방법을 알아보도록 하자.

 

1. 집합에 특정 숫자가 있는지 검사

만약 비트를 사용한 집합 564에 2가 포함되어있는지 알고 싶다면 어떻게 해야 할까?

그 자릿수(2^n)랑 &연산을 해주면 된다.

 

2의 경우 0~9까지 중 세번째 자릿수니까, 564&2^3을 하면

1000110100 & 100 = 8, 결과가 0이 아니기 때문에 2는 포함되어있는것으로 판명되었다.

그러면 포함되어있지 않은 숫자인 6이랑 연산을 해보도록 하자

564&2^7 = 1000110100 & 100000 = 0

 

2. 집합에 숫자 추가하기

특정한 숫자를 추가한다는 것은 해당 자릿수의 비트를 1로 바꿔준다는 것을 의미한다.

집합에 6을 포함시키기 위해서 해당하는 자릿수인 7번째 비트를 1로 바꿔주자.

0을 1로 바꿀것이기 때문에 OR연산을 이용하면 된다.

564 | 2^7 = 1000110100 | 100000 = 1001110100 

 

3. 집합에서 숫자 제거하기

숫자를 제거한다는 것은 해당 자릿수의 비트를 1에서 0으로 바꿔줘야 한다는 것을 의미한다.

564에서 5를 제거해보도록 하자.

1000110100 & 1111011111 = 1000010100 

564 & (~2^5)

성공적으로 제거되었다.