[알고리즘] 비트마스킹(Bitmasking)

비트마스킹이 뭘까? 완전탐색 알고리즘 공부를 하다가 예제에 비트마스킹이 등장했다..

학부때도 비트 연산만 나오면 지루하고 그랬는데.. 계속 피할수만은 없으니!! 이번 기회에 손에 잡힐만하게 공부하자!

비트 연산

비트 연산자

 

&(AND) : 모두 1이면 1

|(OR) : 하나라도 1이면 1

^(XOR) : 서로 다르면 1

~(NOT) : 반전

 

비트 이동 연산자

연산식	설명
x << y	정수 x의 각 비트를 y만큼 왼쪽으로 이동시킨다. (빈자리는 0으로 채워짐)
x >> y	정수 x의 각 비트를 y만큼 오른쪽으로 이동시킨다. (빈자리는 정수 x의 MSB;최상위비트로 채워짐)
x >>> y	정수 x의 각 비트를 y만큼 오른쪽으로 이동시킨다. (빈자리는 0으로 채워짐)

 

 

비트마스크란?

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

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

 

적용

import java.util.*;

public class Main {
	static int N = 4;
    static int[] Nums = {1, 2, 3, 4};
    
	static int solve(int cnt, int used, int val) {
		if(cnt == 2) return val;
    
    	int ret = 0;
    	for(int i = 0; i < N; i++) {
    		if((used & 1 << i) != 0) continue;
        	ret = Math.max(ret, solve(cnt + 1, used | 1 << i, val * 10 + Nums[i]));
    	}
    	return ret;
	}

	public static void main(String[] args) {
		System.out.println(solve(0, 0, 0));
	}
}

 

연산자 우선순위에 따르면 비트 이동 연산자(5순위), 비트AND(8순위), 비트 XOR(9순위), 비트 OR(10순위) 이다.

따라서 1 << i 를 먼저 한 후에 used 와 AND 연산을 한다. AND연산은 모두 1일때 1이 되므로, i번째 비트가 1이면 for문을 빠져나오게 된다. 

이 문제에서는 가장 큰 두 자리수를 구해야 하기 때문에 1, 2, 3, 4중 골랐던 숫자는 넘어가도록 해주기 위해 비트 연산이 사용된 예시였다!