비트마스크(BitMask)

비트마스크에 공부하기 앞서 기본적인 비트연산에 대해 알아야 한다.

비트연산이랑 &(AND), |(OR), ^(XOR), ~(NOT), <<(Shift Left), >>(Shift Right) 로 이루어진 bit 간의 연산을 수행하는 것이다.

해당 연산들을 통해 비트마스크를 이용할 수 있는데, 비트마스크란 쉽게 말해

정수로 집합을 나타낼 수 있는 것이다.

570 = 1000111010 = 2^9 + 2^5 + 2^4 + 2^3 + 2^1

으로 나타내서 1,3,4,5,9의 부분집합을 뜻하는 것이다.

배열보다 정수(비트마스크)로 쓰면 

공간적인 장점, 다른 배열에 넣을 수 있는 점.

0~N-1 의 정수로 이루어진 집합을 나타낼 수 있다.
(1~N 을 쓰려면 2배의 수가 필요 -> 따라서 줄여서 쓰기)

 

비트마스크 연산
S & (1 <<i) i 번째 bit가 값이 있는지 없는지 체크
S | (1<<i) i 번째 bit 추가하기
S & (~(1<<i)) i 번째 bit 제거하기
S ^ (1<<i) i 번째 bit 토글하기(뒤집기)

추가적으로, 연산자 우선순위에 주의하기 위해서 괄호를 써서 처리해야 한다.

1. 부분수열의 합

문제 참고 : https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n,s;
	int ans = 0, sum;
	cin >> n >> s; // 입력받기
	
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i]; // 입력받기

	// 비트마스크 처리
	for (int i = 1; i < (1 << n); i++) {
		sum = 0;
		for (int k = 0; k < n; k++) {
			if (i & (1 << k)) // 해당 자리가 있으면
				sum += arr[k];
		}

		// 정답과 같으면
		if (sum == s)
			ans += 1;
	}
	
	cout << ans << "\n";
}