[알고리즘] 비트 마스크 bitmask

비트 마스크란?

정수의 이진표현을 자료구조로 쓰는 기법을 의미한다.

---

비트 연산자

&	AND	두 비트가 모두 0이면 1
|	OF	두 비트가 모두 1이면 1
^	XOR	두 비트가 서로 반전되면 1
~	NOT	비트의 반전
<<	x << y	x의 각 비트를 y만큼 왼쪽으로 이동하고 오른쪽 빈자리는 0으로 채움
>>	x >> y	x의 각 비트를 y만큼 오른쪽으로 이동하고 왼쪽 빈자리는 최상위 부호 비트와 같은 값으로 채움
>>>	x >>> y	x의 각 비트를 y만큼 오른쪽으로 이동하고 왼쪽 빈자리는 0으로 채움

---

부분 집합

비트 마스크를 이용하여 공집합부터 꽉찬 집합까지 표현이 가능하다.

배열의 개수가 n인경우 (1<<n)-1로 모든 원소를 가지는 집합의 인덱스를 표현할 수 있다.

부분 집합은 0부터 (1<<n)-1사이가 된다.

 

배열이 {3,2,1}인 경우 부분 집합은 다음과 같고 전체 0부터 (1<<3)-1 = 7까지의 수로 부분 집합을 표현하는 것을 볼 수 있다.

{} -> 000 -> 0
{1} -> 001 -> 1
{2} -> 010 -> 2
{2,1} -> 011 -> 3
{3} -> 100 -> 4
{3,1} -> 101 -> 5
{3,2} -> 110 -> 6
{3,2,1} -> 111 -> 7

---

원소 포함 여부 확인

k라는 수의 n번째 인덱스의 비트가 0인지 1인지 확인할 수 있다.

k & (1<<n)을 수행했을때 0이면 원래 n번째 비트가 0이라는 값이고 0이 아니면 n번째 비트가 1이였다는 뜻이다. 

k를 21이라고 하고 n을 2라고 하자.

2번째 인덱스의 비트가 원래 1이었기 때문에 0이 아닌 결과가 나오는 것을 확인할 수 있다.

21		0	0	0	1	0	1	0	1
1<<2		0	0	0	0	0	1	0	0
4		0	0	0	0	0	1	0	0

---

원소 추가

k라는 수의 n번째 인덱스의 비트를 추가할 수 있다.

k |= (1<<n)을 수행하면 된다.

해당 인덱스의 비트가 원래 1이라면 그대로 1이 나오고 0이었다면 |연산에 의해 해당 인덱스의 비트가 1로 바뀌게 된다. 

k를 21이라고 하고 n을 2라고 하자.

2번째 인덱스의 비트가 원래 1이었기 때문에 해당 인덱스는 1이 나오게 되는 것을 확인할 수 있다.

21		0	0	0	1	0	1	0	1
1<<2		0	0	0	0	0	1	0	0
21		0	0	0	1	0	1	0	1

k를 21이라고 하고 n을 3라고 하자.

2번째 인덱스의 비트가 원래 0이었기 때문에 |연산으로 인해 1로 변한 것을 확인 할 수 있다.

21		0	0	0	1	0	1	0	1
1<<3		0	0	0	0	1	0	0	0
21		0	0	0	1	1	1	0	1

---

원소 삭제

k라는 수의 n번째 인덱스의 비트를 삭제할 수 있다.

k &= ~(1<<n)을 수행하면 된다.

해당 인덱스의 비트만 빼고 나머지 비트를 모두 켠뒤 AND연산을 수행하면 n번째 인덱스만 항상 꺼지게 된다.

k를 21이라고 하고 n을 2라고 하자.

21		0	0	0	1	0	1	0	1
1<<2		0	0	0	0	0	1	0	0
~(1<<2)		1	1	1	1	1	0	1	1
17		0	0	0	1	0	0	0	1

k를 21이라고 하고 n을 3라고 하자.

21		0	0	0	1	0	1	0	1
1<<3		0	0	0	0	1	0	0	0
~(1<<3)		1	1	1	1	0	1	1	1
21		0	0	0	1	0	1	0	1

---

Integer.bitCount(k)	k의 켜진 비트 수 반환
Integer.numberOfTrailingZeros(k)	k의 켜진 최하위 비트 번호 반환