[Algorithm] 비트마스크

• 오늘은 부분집합을 비트연산자를 통해 구현하는 방법에 대해 알아보겠습니다.
•  bit 1인 경우, 그 위치에 맞는 집합의 숫자를 출력하는 형태를 통해 모든 부분 집합의 경우의 수를 나타낼 수 있습니다.
• 특히, 부분집합의 개수는 2^N으로 표현되는데, 이를 1 << N으로 표현할 수 있습니다.
  • 예를 들어 2^5의 경우 32개이며, 1 << 5으로 표현할 수 있습니다. 1 << 5는 0000 0001에 대해 shift연산을 통해 0010 0000으로 표현할 수 있습니다.
• 특히, int [] input = {1,3,4,5,2} 의 경우 0번 인덱스 위치의 1을 구하기 위해서는 2^0, 1번 인덱스 위치의 3을 구하기 위해서는 2^1으로 표현될 수 있습니다.

2

5

4

3

1

 

- 다음은 자바를 통해 구현한 코드입니다.

public class SubSetBitOperation {
	public static void main(String[] args) {
		int[] input = {1,3,4,5,2};
		int N = input.length;
		
		//0001 << N은 부분집합의 최대 개수 2^N과 동일
		//flag는 부분집합의 개수만큼 반복문을 반복함
		for(int flag = 0; flag < (1 << N); flag++) {
			System.out.print(flag+1 + "번째 : ");
			//현 비트열의 상태에 대해 각 원소의 부분집합에 포함 유/무 확인
			for (int j = 0; j < N; j++) {
				if((flag & (1 << j)) != 0) {//j 원소가 부분집합에 포함
					System.out.print(input[j] + " ");
				}
			}
			System.out.println();	
		}
	}
	
}

 

• 다음은 코드 구현에 대해 더 자세히 이해하기 위해 표를 통해 작성해보았습니다.

출력 결과의 일부분