비트마스크

비트 연산을 사용해서 정수로 부분 집합 표현

공간을 절약하기 위해

연산자 & , | , ~ , ^

A	B	~A	A&B	A	B
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

연산자 >> , <<

A << B A를 왼쪽으로 B비트만큼 민다

1 << 0 =1

1 << 1 = 2 10(2)

1 << 2 = 4 100(2)

A << B 는 A x 2^B와 같다.

A >> B 는 A / 2^B와 같다.

0부터 N-1까지 정수로 이루어진 집합을 나타낼 때 사용한다.

1100101

활용법

검사하기

부분집합 A 에 0번째 원소가 포함되어 있는지 검사

A & (1<<0) > 0

부분집합 A 에 5번째 원소가 포함되어 있는지 검사

A & (1<<5) > 0

추가

부분집합 A에 0번째 원소 추가

A | (1<<0)

부분집합 A에 2번째 원소 추가

A | (1<<2)

제거

부분집합 A에 0번째 원소 제거

A & ~ (1<<0)

부분집합 A에 4번째 원소 제거

A & ~ (1<<4)

토글 (포함되어있다면 제거 , 없다면 제거하기)

부분집합 A에 0번째 원소 토글

A ^ (1<<0)

부분집합 A에 4번째 원소 토글

A ^ (1<<4)

각 부분집합의 합 구하기

for (int i = 1; i < (1 << N); i++) {
			int sum = 0;
			for (int k = 0; k < N; k++) {
				if ((i & (1 << k)) > 0) {
					sum += arr[k];
				}
			}
			check[sum] = true;
		}