비트와 부분집합

비트연산

& (AND) : 두 비트가 모두 1일 경우에만 1
| (OR) : 두 비트 중에서 하나라도 1이면 1
^ (XOR) : 두 비트가 같으면 0, 다르면 1
~ (NOT) : 각 비트를 반전 (0이면 1, 1이면 0)
<< : 비트를 왼쪽으로 이동

원소가 n개인 부분집합의 총 갯수 : 1 << n
-> ex) n이 4이면, 갯수는 16개 (비트: 0000~1111)

// 비트를 활용해 배열의 쌍을 이루지 않는 값 리턴 - {9, 3, 9, 3, 9, 7, 9}
int answer = 0;

for(int i = 0; i < A.length; i++) {
   answer = answer ^ A[i];
}

return answer;

집합의 원소 개수

Integer.bitCount(int i) : 정수를 매개변수로 넣었을때 그 정수의 1 의 개수를 반환
-> 1101는 3개를 반환