[Algorithm] 비트 마스킹

 

 

화이팅

개요

알고리즘 공부를 하면서 비트마스킹이라는 기법이 존재한다는 것을 알았고 자바를 통해서 비트를 어떤식으로 쓸 수 있는지 감을 좀 잡고 비트를 어떻게 사용하고 어떻게 쓸 수 있는지 알아보았다.

본론

비트 마스킹은 말그대로 비트를 사용한 연산들을 의미한다.

비트 연산은 low level 연산이기 때문에 기존의 연산들보다 속도가 높고 메모리 사용량도 훨씬 낮다.

집합 혹은 true/false 대신에 비트 마스킹을 사용할 수 있는 것으로 보이며 자바의 boolean 타입은 1Byte지만 사실 비트 연산으로 이것을 표현하면 1비트로 표현할 수 있다.

집합과 true false

비트 마스킹을 사용해서 집합을 표현할 수 있다.

// 공집합
int x = 0;
// x 집합에 y 추가 (y비트를 1로 세트한다.)
x |= (1 << y);
// x 집합에 y 제거 (y비트를 0으로 세트한다.)
x &= ~(1 << y);
// x 집합에 y가 존재하는지 체크
(x & (1 << y) == (1 << y))
// x 집합에 모든 원소를 채운다. (집합의 최대 크기가 y라고 가정)
x = (1 << y+1) -1;

위와 같이 비트를 통해서 boolean[]을 표현하거나 집합을 표현할 수 있다.

다음 포스트는 비트 마스킹을 이용해서 boolean[]을 대체한 결과를 테스트해본 포스트이다.

[JAVA] 백준 2961

 

다음 포스트는 비트 마스킹을 이용해서 집합을 표현한 문제이다.

[JAVA] 백준 15787

 

결론

비트 마스킹을 사용하면 boolean[]을 대체할 수 있고 집합을 표현할 때 속도와 메모리 효율을 높일 수 있다.