비트마스크 (2)

비트마스크

정수의 이진수 표현을 자료구조 기법으로 쓰는 테크닉

 

집합의 구현

비트마스크의 사용사례로 집합의 구현이 있다.

-> N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다.

이때 원소 i가 집합에 속해 있는지 여부는 2^i을 나타내는 비트가 켜져 있는지 여부로 나타낸다.

예를 들어 여섯 개의 원소를 갖는 집합 {1, 4, 5, 6, 7, 9}을 표현하는 정수는 754임을 다음과 같이 알 수 있다.

 

2^1 + 2^4 + 2^5 + 2^6 + 2^7 + 2^9 = 10 1111 0010 = 754

 

피자집 예제

피자집 주문 시스템

0부터 19까지의 번호를 갖는 스무 가지의 토핑이 있으며, 주문시 토핑을 넣기/넣지 않기를 선택할 수 있다.

 

공집합과 꽉 찬 집합

토핑을 올리지 않은 피자와 모든 토핑을 올린 '전부 다' 피자를 표현하려한다.

 

토핑을 올리지 않은 피자(공집합)

int noToppingPizza = 0;

꽉 찬 집합

int fullToppingPizza = (1 << 20) - 1;

 

원소 추가

집합의 가장 기초적인 연산은 원소를 추가하고 삭제하는 것이다.

비트마스크를 사용한 집합에서 원소를 추가한다는 것은 해당 비트를 켠다는 것이다.

토핑 목록에 페퍼로니를 추가하고 싶다.

페퍼로니의 번호 p(0<= p < 20)가 주어질 때, 다음 코드로 집합 toppings에 페퍼로니를 추가..

toppings |= (1 << p);

1을 왼쪽으로 p비트 시프트하면 p번 비트만 켜진 정수가 되므로 이 값과 toppings를 비트별로 OR연산하면 해당 비트는 반드시 켜지게 된다.

toppings에 이미 페퍼로니가 들어가 있을 경우 값이 변하지 않는다는 사실 유념

 

원소의 포함 여부 확인

집합 toppings에 페퍼로니가 포함되어 있는지...

if( (toppings & (1 << p)) == (1 << p) )
	System.out.println("pepperoni is in!");
else if( (toppings & (1 << p)) == 0 )
	System.out.println("NO pepperoni!");

 

원소의 삭제

페퍼로니 삭제는 다음과 같이

toppings &= ~(1 << p);

toppings -= (1 << p); 는 안된다.

 

원소의 토글

켜지면 끄고, 꺼지면 켠다.

toppings ^= (1 << p);

 

두 집합에 대해 연산하기

* int added = ( a | b );			// a와 b의 합집합
* int intersection = ( a & b );	// a와 b의 교집합
* int removed = ( a & ~b );		// a에서 b를 뺀 차집합
* int toggled = ( a ^ b);			// a와 b중 하나에만 포함된 원소들의 집합

위 코드의 수행시간은 원소 하나에 대해 수행하는 것과 다를게 없다.

 

집합의 크기 구하기

1.

public static int bitCount(int x) {

	if(x == 0) return 0;

	return x % 2 + bitCount(x / 2);
}

2.

Integer.bitCount(toppings);

 

최소 원소 찾기

"이 정수의 이진수 표현에서 끝에 붙어 있는 0이 몇 개 인가?"

켜져 있는 최하위 비트 밑의 비트들은 전부 0일테니, 이 연산은 켜져 있는 최하위 비트의 번호를 반환하게 된다.

다음은 32비트 부호 없는 정수 toppings에서 켜져 있는 최하위 비트의 위치를 구하는 코드..

Integer.numberOfTrailingZeros(toppings);

참고로 Integer 클래스에 주석 중에

 * <p>Implementation note: The implementations of the "bit twiddling"
 * methods (such as {@link #highestOneBit(int) highestOneBit} and
 * {@link #numberOfTrailingZeros(int) numberOfTrailingZeros}) are
 * based on material from Henry S. Warren, Jr.'s <i>Hacker's
 * Delight</i>, (Addison Wesley, 2002).

 

최하위 비트의 번호 대신 해당 비트를 직접 구하고 싶다면...

int firstTopping = (toppings & -toppings);

 

최소 원소 지우기

toppings &= (toppings - 1);