코딩테스트를 위한 자바(java) 비트마스크 - 6

 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트 마스크(bitmask)라고 부른다.

 

엄밀히 말하면 자료구조는 아니지만 코딩 테스트를 할 때 유용하게 사용 가능하다.

 

비트 마스크를 알기 전에 비트 연산에 대해서 알 필요가 있다.

 

비트 마스크를 이용하면 얻을 수 있는 장점이 3가지가 있다.

 

• 더 빠른 수행 시간
• 더 간결한 코드
• 더 작은 메모리 사용량

ex) { 1,3,5,7,9 }를 원소로 가지는 집합을 표현할 때

방법 1 : int[] arr = { 1,3,5,7,9 };

방법 2 : 101010101(2)
(비트마스크)

 

 

 

N비트 일 때 오른쪽부터 순서대로 0번째 비트, 1번째 비트, 2번째 비트... N-1번째 비트

공집합	0
꽉 찬 집합	int full = (1<<p) -1;	(1<<20) : 1오른쪽에 0이 p개   ->  -1을 하면 1이 p개
p번 원소 추가하기	element |= (1<<p) ;	(1<<p) : 1 오른쪽에 0이 p개 : p번 원소를 나타냄 |= : or연산을 통해 원소를 추가
p번 원소 가져오기	element & (1<<p);	(1<<p) : 1오른쪽에 0이 p개 : p번 원소를 나타냄 &= : and 연산을 통해 p번 원소가 1인지 0인지 확인
p번 원소 0으로 바꾸기	element &= ~(1<<p);	~(1<<p) : 0 오른쪽에 1이 p개 &= : and 연산을 통해 p번 원소를 0으로 바꿈.
p번 왼쪽원소 모두 0으로 바꾸기	element &= ((1<<p)-1);	(1<<p)-1 : 1이 p개인 원소 &= : and 연산을 통해 왼쪽 원소 0으로 바꿈
p번 오른쪽 모두 0으로 바꾸기	element &= (-1 << p);	(-1<<p) : 왼쪽은 모두 1이고 오른쪽에 0이 p개 * -1은 모든 원소가 1 임
p번 원소 원하는 값 넣기	element &= ~(1<<p) | ((val? 1:0)<<p);	p번 원소 0으로 초기화해 준 후 -> boolean val; 입력을 받은 후  (val? 1:0) : val이  true일 때 1, false일 때 0 반환 p번 인덱스가 val 에 해당하는 값으로 바뀜.
원소 중 1인 것 개수 출력	Integer.bitCount(element);

 

비트 카운트를 이용해 N개중 M개를 뽑아 검사하는 방법에 대해서 살펴보자.

 

1. 먼저 N개를 검사하는 경우를 비트 마스크로 표현하면 다음과 같다.

int N = 3;
int M = 2;
for(int j = 0 ; (1<<N) > j ; ++j) {
	System.out.print(j+ " ");
	}
    //결과 0 1 2 3 4 5 6 7

2. 비트 중 1의 개수, 0의 개수를 조건으로 사용할 수 있다. ( N개 중 M개를 선택하는 경우 )

int N = 3;
int M = 2;
for(int j = 0 ; (1<<N) > j ; ++j) {
	if(Integer.bitCount(j) == M) {
    System.out.print(j + " ");
	}
}
// 결과 3 5 6   // 011 101 110

3. 추가적으로 001 , 010, 100 bit mask를 만들어 and 연산을 이용해 해당 비트를 출력하면 된다.

 

( N개 중 M개를 선택하는 경우 원소 출력)

int N = 3;
int M = 2;
for (int j = 0; (1 << N) > j; ++j) {
	if (Integer.bitCount(j) == M) {
		for (int i = 0; i < N; ++i) {
			if (((1 << i) & j) > 0) {
				System.out.print(i+ " ");
			}
		}
		System.out.println();
	}
}
결과:
0 1 
0 2 
1 2 

N = 5;
M = 4; 일때
결과:
0 1 2 3 
0 1 2 4 
0 1 3 4 
0 2 3 4 
1 2 3 4