개요

컴퓨터에서는 기본적으로 모든 값을 이진수로 표현하는데, 이 특성을 이용하여 ***“정수의 이진수를 일종의 자료구조로 사용하는 기법”***이 비트마스킹이다. 즉 알고리즘이 아닌 일종의 자료 구조.

단순 true, false만을 저장하기 위한 bool 배열을 충분히 대체할 수 있다. ”있다, 없다” 혹은 “맞다, 아니다”같은 개념을 저장할 수 있다.

간혹 코딩 고인물들이 브론즈 실버 문제에다가 행위예술 해둔 것을 본 적이 있는데, 지금 생각해보면 그게 비트마스킹이었고 극한까지 메모리를 아끼기 위한 흔적이었다고 해석된다.

익숙해지면 상당히 유용할 것으로 예상. 대신 정수 값의 바이트 수가 언어마다 다른 경우도 있고, 논리 연산자의 우선순위도 다르기 때문에 언어에 대한 높은 이해도를 요구한다. 가용한 비트 수와 사용하려는 원소 수를 잘못 계산하면 오버플로우가 발생하거나 집합 연산의 결과가 이상하게 나올 수 있다.

왜 사용하는가?

1. 시간

비트 단위로 다루기 떄문에 당연히 비트 연산을 사용하고, O(1)으로 구현할 수 있는 것들이 많다. 연산 횟수가 적을 때는 크게 차이가 안나지만, 연산 횟수가 늘어날수록 시간 차이가 많이 난다.

2. 간결한 코드

집합 연산같은 것들을 비트연산자 한 줄로 작성할 수 있어서 간결하다.

3. 적은 메모리 사용

같은 용도로 사용되는 bool 배열에 비해서 메모리 사용량이 훨씬 적다. 원소가 10개인 비트마스크는 그냥 10비트가 전부인데, bool 배열을 사용하려면 bool 자료형의 크기 * 10만큼 사용된다.

비트 연산자

이진수를 다루기 때문에 비트 연산자가 사용된다. 웬만한건 논리회로에서 배웠던 것과 동일하고, 비슷한 기법도 많이 사용된다.

a % b ## AND
a | b ## OR
a ^ b ## XOR
~a    ## NOT
a << b ## L_SHIFT: a를 b만큼 왼쪽으로
a >> b ## R_SHIFT: a를 b만큼 오른쪽으로

L_SHIFT