부분집합구하기( 비트마스킹, 비트연산자, 비트마스크)

SHIFT연산자 (<<, >>) : 모든 비트를 해당 방향으로 밀어줌 (곱셈, 나눗셈의 효과)

public class Shift {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int number =1; // 0000 0001
        System.out.println("원래 숫자 : "+ number); // 1 출력  

        number = number << 1; // 0000 0010
        System.out.println("왼쪽으로 1칸 쉬프트 : "+ number);// 2 출력  

        number = number << 2; // 0000 1000
        System.out.println("왼쪽으로 2칸 쉬프트 : "+ number);// 8 출력  

        number = number >> 1; // 0000 0100
        System.out.println("오른쪽으로 1칸 쉬프트 : "+ number);// 4출력    
    }
}

부분집합 구하기 : ( 1 << N ) == (2^n) 따라서 부분집합의 전체 갯수(공집합 포함) / 백준 1182

주의 : 백준 1208 (배열 범위 40은 비트마스크 자료형 int 로 해결 불가능 !!)
signed int [-(2^31) ~ 2^31-1 ] 이기 때문에 2^40 를 해결하려면 다른 방법 필요

public class Subset {

    public static int[] arr = {1,2,3};
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int N = arr.length; // 배열 전체 길이  
        for(int i=0; i< (1 << N); i++) // 0 ~ 7 
        {
            for(int j=0; j < N; j++) // 원소의 갯수만큼 for문 
            {
                if( ( i&(1<<j) ) != 0 )// i의 j 번째 bit가 1인지 아닌지 확인
                {
                    System.out.print(arr[j]+" ");
                }
            }
            System.out.println();
        }
    }
}
출력 결과 
(공집합)
1
2
1 2
3
1 3
2 3
1 2 3

WonYong-Jang / algorithm

부분집합구하기( 비트마스킹, 비트연산자, 비트마스크) #7

SHIFT연산자 (<<, >>) : 모든 비트를 해당 방향으로 밀어줌 (곱셈, 나눗셈의 효과)

부분집합 구하기 : ( 1 << N ) == (2^n) 따라서 부분집합의 전체 갯수(공집합 포함) / 백준 1182

leetcode 338 counting bits