비트마스킹

비트마스킹

비트연산

비트 이동 연산자

• x << y : x의 각 비트를 y만큼 왼쪽으로 이동. 오른쪽 빈자리는 0으로 채워짐
• x >> y : x의 각 비트를 y만큼 오른쪽으로 이동. 왼쪽 빈자리는 x의 최상위 부호 비트와 같은 값으로 채워지게 된다.
• x >>> y : x의 각 비트를 y만큼 오른쪽으로 이동. 왼쪽 빈자리는 0으로 채워진다.

비트 논리 연산자

• &(AND) : 두 비트 모두 1이면 1
• |(OR) : 두 비트 1개만 1이면 1
• ^(XOR) : 두 비트가 서로 다르면 1
• ~(NOT) : 보수

비트마스킹

• 비트 연산에 사용되는 다중 비트들을 싱글비트 연산 작업에서 켜고 끄거나 상호반전 시킬 수 있다.

사용되는 이유

• DP나 순열 등, 배열 활용으로 해결할 수 없는 문제
• 작은 메모리와 빠른 수행시간으로 해결가능!(조건 : 원소의 수가 많지 않아야함)
• 집합을 배열의 인덱스로 표현가능
• 코드가 간결해진다

비트마스킹을 이용하여 부분집합 구하기

배열 [3,4,5,6]이 있을 때 이 배열의 부분집합은
[], [3], [4], [5], [6], [3,4], [3,5] ... [3,4,5,6] 이 된다

이 경우를 인덱스로 표현하여 접근해볼 수 있다.
[3,4,5,6] = 1111
[3,6] = 1001
[3] = 1000
[] = 0000

1111 을 10진수로 변환하면 15. 즉, 0 부터 15까지로 부분집합 표현이 가능하다.

부분집합 구해보기

class Main{
	static int nums = {1,2,3,4,5};
    public static void main(String[] args){
    	subset();
    }
    public static subset() {
    	for(int flag=0; flag<(1<<nums.length); flag++){
        	for(int i=0; i<nums.length; i++){
            	if((flag&(1<<i))!=0){
                	system.out.print(nums[i]+" ");
                }
            }
            System.out.println();
        }
    }