비트 연산

내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리할 수 있다. 그래서 비트연산으로 표현하는 것은 메모리 측면이나 속도 측면에서 기존 표현보다 효율적이다.

&

비트마다 AND연산을 해서 두 비트가 모두 1일 경우에만 1이 된다
ex) 0b 1111 & 0b 0011 = 0b 0011

|

비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 된다.
ex) 0b 1100 | 0b 1010 = 0b 1110

^

XOR연산. 둘중에 하나만 1일때 1을 반환한다. 이를 이용해 특정 비트를 toggle할 수 있다

~

NOT연산. 모든 비트를 1이면 0으로 0이면 1로 반전합니다.
ex ) ~0b 1100 = 0b 0011

>>

1 비트 오른쪽으로 이동합니다.
시프트 연산 >>은 2의 거듭제곱을 나누기입니다.

ex) 0b 110(6) >> 1 = 0b 011(3)
6/2^1=3

<<

1 비트 왼쪽으로 이동합니다.
시프트 연산 <<은 2의 거듭제곱을 곱하기
ex) 0b 110 << 1 = 0b 1100
6*2^1=12

비트 연산을 이용하여 부분집합 만들기

n개의 원소에 대하여 부분집합의 개수는 2^n개이다.
n개의 원소에 대하여 부분집합을 각각의 원소를 0(미포함)/1(포함)으로 나타낼 수 있다.
이 방식을 비트연산으로 표현하는 것이다.

{1,2,3} 3개의 원소에 대한 부분집합은
{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}이다.
이를 3자리비트로 표현하면
001, 010, 100, 011, ... 처럼 표현이 가능하다. 이것은 1부터 2^n까지의 수를 비트로 표현한 수가 된다.
따라서 1부터 2^n까지 반복하면서 비트가 1인 자리의 인덱스에 대한 값만 출력하면 부분집합을 완성할 수 있다.

        int n = 3;
        // 1<<n은 2^n과 동일하다
        for(int i=0; i<(1<<n); i++){
            System.out.println(i);
            System.out.print("[");
            // n개의 비트에 대해
            for(int j=0; j<n; j++){
                if((i & (1<<j)) != 0){
                    System.out.print(j+",");
                }
            }
            System.out.println("]");
        }

10진수	이진수	{}
0	000	{}
1	001	{1}
2	010	{2}
3	011	{1,2}
4	100	{3}
5	101	{1,3}
6	110	{2,3}
7	111	{1,2,3}

---

참고
https://sangdo913.tistory.com/7
http://dumpsys.blogspot.com/2015/03/algorithm-binary-counting-power-set.html
https://meylady.tistory.com/22