비트연산자/마스킹

출처: https://blog.naver.com/jhc9639/222310927725

 

1. Shift 연산 특징

a << b  =   a * (2^b)

a >> b  =   a / (2^b)

#include<iostream>

using namespace std;

int main(void) 
{
	// a << b  =  a * (2^b)
	int a = 5;
	int b = 2;
	// 5  *  (2 ^ 2 ) = 20
	cout << (a << b) << endl;
	cout << (a >> b); // 5  / (2^2) = 1;
}

 

2. Weird 연산자 특징

~ :  One's Complement  1의 보수 연산자(비트 반전), weird 연산자

 ~(value) = -(value + 1)

#include<iostream>

using namespace std;

int main(void) 
{
	// ~ :  One's Complement  1의 보수 연산자(비트 반전), weird 연산자
	// ~(value) = -(value + 1)
	
	
	/*
	000000011 (3)
	111111100 (~3)
	*/
	cout << ~3;  // -4
}

 

음수(-value) : 비트를 반전 한 수(~value) + 1

-value = ~value + 1

~value = -(value + 1)

-16은?

16 = 00010000 

11101111 + 1 = 11110000 (~16 + 1 = -16) 

 

~16 == -(16 + 1) = -17.

 + 1 

------

-16 ( -17 + 1)

#include<iostream>

using namespace std;

int main(void) 
{
	cout << ~16+1;  // -16
}

 

3. 활용 ( idx 번째 비트끄기)

암기

idx번째 비트끄기	S &= ~(1<<idx)
idx번째 비트 XOR 연산	S ^= (1<<idx)
최하위 켜져있는 비트 찾기	idx = (S & -S)
크기가 n인 집합의 모든 비트를 켜기	(1<<n) -1
idx번째 비트를 켜기	S |= (1 << idx)
idx번째 비트가 켜져 있는지 확인	if(S & ( 1<<idx))

 

 

4. 보수

https://yiyj1030.tistory.com/83

2의 보수란?? 쉬운 설명으로 궁금증 해결.. (비트 연산)

 

---

비트마스킹 

#1  경우의 수 (조합)

#include<iostream>

using namespace std;

/*
공간이 4개면 2^4 이 경우의 수
0000 (공집합)
0001  0 인덱스  사과
0010  1 idx  딸기
0011  0, 1 idx  사과/딸기
0100  2 idx  포도
0101  0, 2 idx   사과/포도
0110
0111
1000
1001
1010
1011
1100
1101
1110 1,2,3 idx 딸기/포도/배
1111  0~3  idx 사과/딸기/포도/배
*/
const int n = 4;
int main(void) 
{
	string a[n] = { "사과","딸기","포도","배" };
	for (int y = 0; y < (1 << n); ++y) {
		string ret = "";
		for (int x = 0; x < n; ++x) {
			if (y & (1 << x)) {  //  y가 0일때는 공집합.  1일때는 x가 0일때 if조건 성립(사과). y가 2일 때, x가 1일때 성립(딸기). y가 3일때 x는 0, 1 일때 성립(사과/딸기).
				ret += a[x] +" ";
			}
		}
		cout << ret << endl;
	}
}

#2 경우의 수 (조합)

visited를 대체하는 비트마스킹.

#include<iostream>

using namespace std;

const int n = 4;
string a[4] = { "사과","딸기","포도","배" };
void go(int num) {
	string ret = "";
	for (int x = 0; x < n; ++x) {
		if (num & (1 << x)) ret += a[x]  + " ";
	} 
	cout << ret << endl;  // 사과,딸기 / 사과,포도 / 사과,배
	return;
}
int main(void) {
	//visited 플래그 없이 합(bit)연산자로 출력.  사과의 짝.  
	for (int x = 1; x < n; ++x) {
		go(1 | (1 << x));
	}
	return 0;
}

---

비트마스킹의 한계는 n이 31까지(int형)

2^30승은 약 10억이 된다. 그 이후의 값들은 시간복잡도를 많이 초과하기에 비트마스킹은 보통 30~31까지 경우의 수만 표현가능.

 

문제에서 n <=30 이고 경우의 수를 구하는 문제면 비트마스킹으로 풀이가능.