[Algorithm] 비트마스킹(Bitmasking) (Java)

비트(Bit)와 비트마스킹(Bitmasking)

비트마스킹 기법에 대해 학습한 내용을 정리해둔다.
자바의 비트 연산자와 비트 이동 연산자를 알아보고, 비트마스킹이 무엇인지 알아보도록 하겠다.

자바 비트 연산자

• &
  • bit AND 연산자
  • 비교하는 비트가 모두 1이면 1

# a = 22, b = 14
# a & b
         00010110
(AND) &  00001110
------------------
         00000110

• |
  • bit OR 연산자
  • 비교하는 비트 중 하나라도 1이면 1

# a = 22, b = 14
# a | b
         00010110
 (OR) |  00001110
------------------
         00011110

• ^
  • bit XOR 연산자
  • 양쪽 비트가 같으면 0, 다르면 1

# a = 22, b = 14
# a ^ b
         00010110
(XOR) ^  00001110
------------------
         00011000

• ~
  • bit NOT 연산자
  • 비트를 반전시킨다.

# a = 22
# ~a
(not) ~  00010110
------------------
         11101001

자바 비트 이동 연산자

• <<
  • 연산자 기준 왼쪽에 있는 수를 오른쪽에 있는 수 만큼 왼쪽으로 비트 이동한다.
  • 우측의 빈자리는 0으로 채워진다.
  • MSB(가장 왼쪽에 위치한 비트)가 1이 되면 음수로 전환된다.
  • a << b 이면 a를 b만큼 왼쪽으로 비트 이동한다.
• >>
  • 연산자 기준 왼쪽에 있는 수를 오른쪽에 있는 수 만큼 오른쪽으로 비트 이동한다.
  • 좌측의 빈자리는 연산자 기준 왼쪽 수의 MSB와 같은 값으로 채워진다.
  • a >> b 이면 a를 b만큼 오른쪽으로 비트 이동한다.
• >>>
  • 연산자 기준 왼쪽에 있는 수를 오른쪽에 있는 수 만큼 오른쪽으로 비트 이동한다.
  • 좌측의 빈자리는 0으로 채워진다.
  • a >>> b 이면 a를 b만큼 오른쪽으로 비트 이동한다.

      14 : 00001110
 14 << 2 : 00111000 # 우측 빈자리는 0으로 채워진다.
 14 >> 2 : 00000011 # 좌측 빈자리는 14의 MSB와 같은 값으로 채워진다. 여기서는 0이다.
14 >>> 2 : 00000011 # 좌측 빈자리는 0으로 채워진다.

비트 연산자와 비트 이동 연산자 활용

가장 우측의 비트를 1번째 비트라고 하자.
이 때, i번째 비트에 가할 수 있는 연산은 다음과 같다.

• i번째 비트 조회
  • n & (1 << (i-1))
• i번째 비트를 1로 변경
  • n | (1 << (i-1))
• i번째 비트를 0으로 변경
  • n & ~(1 << (i-1))

비트마스크

비트마스크(bitmask)란 정수의 2진수 표현을 자료구조로 쓰는 기법을 말한다.
비트마스크의 장점은 다음과 같다.

• 수행시간이 빠르다.
  • 비트마스크 연산은 비트 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조보다 빠르게 동작한다.
  • 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기 때문에 큰 속도 향상을 기대할 수는 없지만, 여러번 수행해야 하는 경우, 큰 속도 향상을 가져올 수 있다.
• 코드가 간결해진다.
  • 조건문, 반복문을 사용하지 않고 다양한 집합 연산들을 통해 코드를 간결하게 작성할 수 있다.
• 적은 메모리를 사용한다.
  • 비트는 1과 0 두 가지 경우만을 가진다.
  • 만약 비트가 10개가 있다면 2^10의 경우를 10비트 이진수 하나로 표현이 가능하다.
  • 이 처럼 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 더 많은 데이터를 미리 계산하여 저장해 둘 수 있다는 장점이 있다.
  • 이와 같은 특성 덕분에 DP에 매우 유용하다.

예를 들어

비트마스킹을 이용한 배열의 부분집합 구하기

아래는 배열 arr이 주어졌을 때, 원소의 개수가 2인 arr의 부분집합을 구하는 예시이다.

int[] arr = {1, 2, 3, 4, 5};

for (int i = 0; i < 1 << arr.length; i++) {
    // Integer.bitCount(k) : k를 이진수로 표현했을 때 1의 개수 리턴
    if (Integer.bitCount(i) == 2) {
        for (int j = 0; j < arr.length; j++) {
            if ((i & (1 << j)) > 0) {
                System.out.printf("%2d", arr[j]);
            }
        }
        System.out.println();
    }
}