1. idx 번째 비트 끄기

S &= ~(1<<idx)

ex) 10010 (18) 의 1번째 비트 끄기

18 &= ~(1<<1)

2. idx 번째 비트 XOR 연산 (0은1로, 1은 0으로)

S ^=(1<<idx)

ex) 10010(18) 의 0번째 비트 바꾸기

18 ^= (1<<0)

3. 최하위 켜져있는 비트 찾기

idx = (S&-S)

ex) 10010 (18) 의 최하위 켜져있는 비트? 1번째 비트

4. 크기가 N 인 집합의 모든 비트를 켜기

(1<<N) -1

5. idx 번째 비트 켜기

S |= (1<<idx)

ex) 10010 (18) 0번째 비트 켜기

18 |= (1<<0)

6. idx 번째 비트가 켜져있는지 확인

if( S & (1 << idx)) {켜져있습니다.}
else{꺼져있습니다.}

10010 (18) 3번째 비트 확인

if(18 & (1 << 3)) 

비트마스킹

어떤 특정 원소를 찾을때 시간복잡도를 줄이기 위해서 boolean 배열의 역할을 하는 “하나의 숫자” 를 만들어서 “비트 연산자” 를 통해 탐색, 수정등의 작업을 하는 것

비트마스킹을 이용한 경우의 수

예를들어 {사과,딸기,포도,배} 의 모든 경우의 수 ??

각각의 요소는 2개의 상태 값(있거나, 없거나)을 가지기 때문에 2^4 = 16

비트마스킹으로 표현

#include<bits/stdc++.h>
using namespace std;
const int n = 4;
int main(){
	string a[n]={"사과","딸기","포도","배"};
	for(int i = 0; i< (i<<n); i++){
		string ret = "";
		for(int j = 0; j < n; j++){
			if(i & (1 << j)){  // j 번째 비트가 켜져있는지 확인 
				ret += (a[j] + " ");
			}
		}
		cout<<ret<<'\n';
	}
	return 0;
}

비트마스킹을 이용한 매개변수 전달

사과라는 매개변수가 포함이 되어있고 사과+포도, 사과+배, 이런식의 매개변수를 더하는 것을 구현하고 싶다면?

#include<bits/stdc++.h>
using namespace std;
const int n = 4;
string a[n]={"사과","딸기","포도","배"};

void go (int num){
	string ret= "";
	for(int i=0; i<4; i++){
		if(num & (1 << i)) ret += a[i] + " "; // i번째 비트가 켜져있는지
	}
	cout<< ret << '\n';
	return ;
}

int main(){
	for(int i = 1; i < n; i++){
		go(1 | (1<<i)); //i 번째 비트 켜기
	}
	return 0;
}