bit masking

1. 비트 마스킹

• 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이를 이용해서 정수의 이진수 표현을 아예 자료구조로 쓰는 기법을 비트마스크라고 한다.

2. 비트 연산자 연습

/**
 * 두 수가 모두 1일때만 1, 나머지는 0
 * */
public class AND {
    public static void main(String[] args) {
        int a = 4;  //100
        int b = 7;  //111

        System.out.println(a & b);  //100
    }
}

/**
* 둘 중 하나라도 1이면 1, 나머지는 0
* */
public class OR {
    public static void main(String[] args) {
        int a = 2;  //010
        int b = 5; //101

        System.out.println(a | b);  //111 = 7
    }
}

/**
 * 모든 비트에 NOT 연산을 한다.
 * */
public class NOT {
    public static void main(String[] args) {
        int a = 3;  //011

        System.out.println(~a); //100 = -4

        int b = 7;  //111 -> 0000 .... 00000111 = 7
        System.out.println(~b); //000 -> 1111.... 11111000 = -8
    }
}


/*
* 서로 다르면 1, 같다면 0
* */
public class XOR {
    public static void main(String[] args) {
        int a = 3;      //011
        int b = 5;      //101

        System.out.println(a ^ b);  //110 = 6
    }
}


public class Shift {
    public static void main(String[] args) {
        System.out.println(9 << 2);
        //1001 -> 0010 0100 = 4+32 = 36

        System.out.println(Integer.toBinaryString(15));
        System.out.println(15 << 3);
        //1111 -> 0111 1000 = 8+16+32+64 = 24+96 = 120

        System.out.println(4 >> 2);
        //100 -> 001 = 1

        System.out.println(1 << 2);
        //001 -> 100 = 4
    }
}

3. 집합

/**
* 집합
 * - 원소를 0 ~ n-1 까지 번호를 부여한다.
 * - 번호에 해당하는 비트가 1이면 원소가 포함, 0이면 불포함이라고 판단
* */
public class Set {
    public static void main(String[] args) {
        //{A, B, C, D, E, F, G}
        //0, 1, 2, 3, 4, 5, 6

        /*
        * {A} 의 부분집합 = 1000000 = 64
        * {C, F}의 부분집합 = 0010010 = 2+16 = 18
        * */
    }
}

/**
 * 집합에 원소 추가
 * - 현재상태인 cur 이 존재할 때, p번 원소를 추가한다고 가정.
 * - cur 에서 p번째 비트만 1로 바꾸어주어야 한다.
 * */
public class SetAdd {
    public static void main(String[] args) {
        int b = 16;     //10000
        //목표 : 11010 = 26
        System.out.println(b | 1 << 3 | 1 << 1);

        int a = 32;     //100000
        //뒤에서 4번째 index에 원소를 추가하고자 할때, 만들려는 수는 101000

        System.out.println(Integer.toBinaryString(1 << 3));
        System.out.println(a | (1 << 3));       //40
    }
}

/**
 * 원소 삭제
 * - current 에서 p번 원소만 삭제
 * - p번 비트를 0으로 바꾸어주어야 한다.
 * */
public class SetRemove {
    public static void main(String[] args) {
        int p = 40;     //101000
        //3번째 원소를 제거하려면? 목표하는 수는 100000 = 32
        System.out.println(Integer.toBinaryString(1 << 3));
        System.out.println(p & ~(1 << 3));      //32
    }
}

/**
 * 1이면 0, 0이면 1로 변환
 * */
public class SetToggle {
    public static void main(String[] args) {
        int a = 7;  //111
        //목표 : 101 = 5
        System.out.println(a ^ 1 << 1);
    }
}

/**
 * 집합의 크기 구하기
 * */
public class SetSize {
    public static void main(String[] args) {
        System.out.println(bitCount(15));
    }

    private static int bitCount(int num) {
        if (num == 0) {
            return 0;
        }
        return num % 2 + bitCount(num / 2);
    }
}

/**
 * 합집합 구하기
 * */
public class SetCombine {
    public static void main(String[] args) {
        //a | b : 합집합
        //a & b : 교집합
        //a & ~b : 차집합
        //a ^ b : 합집합 - 교집합 = a와 b 중 하나에만 포함된 원소
    }
}

4. 참고

• https://travelbeeee.tistory.com/451