C++ 개념 공부/알고리즘

[C++] 비트 마스킹(비트 연산)

taene_ 2024. 2. 29. 12:27

<비트>

- 데이터 타입에는 각 메모리 사용 크기가 있다. int를 표현하자면 4byte(32 bit)의 크기를 가지고, 00000000 00000000 00000000 00000000이 된다. 1byte = 8bit

- 만약 무언가를 있고 없고만 체크한다면 bool 변수 32개를 쓰는 대신, 하나의 비트를 다룰 수있으면 우리는 int하나로 32개의 유무를 표시할 수 있다. 또 비트 연산은 연산 속도도 빠르다.

(만약 2번째 아이템이 있다면 0100 이런식으로 0을 1로 바꾸어 표현함)

 

<비트연산자>

&
비트단위로 AND 연산을 한다. (둘 다 1일 경우에만 1이고, 나머지는 0)
|
비트단위로 OR 연산을 한다. (둘 중 하나라도 1일 경우 1이고, 둘 다 0일 경우에만 0)
^
비트단위로 XOR 연산을 한다. (둘이 같으면 0, 다르면 1)
~
피연산자의 모든 비트를 반전시킨다.
<<
피연산자의 비트 열을 왼쪽으로 이동시킨다. (a<<b // a라는 비트를 b만큼 왼쪽으로 이동 후 뒤에는 0으로 채움 )
>>
피연산자의 비트 열을 오른쪽으로 이동시킨다.

 

<비트마스킹 활용법>

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))

 

<비트마스킹 예시>

1. 공집합 S 만들기

// int -> 4byte = 4*8bit
int s = 0;	// 00000000 00000000 00000000 00000000 공집합 만들기

 

2. idx번째 비트 켜기

int s = 0;
int idx = 3;
s |= (1 << 3);	// 0000 | 1000 == 1000

 

3. idx번째 비트 끄기

int n = 15; // 1111 
int idx = 2;  
n &= ~(1 << idx); // 1111 & 1011 == 1011(11)

 

4. idx번째 비트가 있는지 확인하기

int n = 5; // 0101
int idx = 3;
string a = n & (1 << idx) ? "yes" : "no";	// 삼항연산자
// &연산자이므로 0이 나오면 idx번째에 비트가 없으므로 a=="no", 
// 양수가 나오면 idx번째에 비트가 있으므로 a=="yes"
if(s & (1<<3))
{
	cout << "yes" << endl;
}
// ex1) s - 0000 1000 & 1000 == 1000(8) - true
// ex2) s - 0000 0100 & 1000 == 0000(0) - false

 

5. 최소(최하위) 비트 끄기

s &= (s-1); // s = 0101 1110 이라고 가정

// (s-1) -> 0101 1110 - 0000 0001 = 0101 1101
// 0101 1110 & 0101 1101 == 0101 1100 (최하위로 켜져있던 1번째 비트를 끔)

 

6. 최소(최하위) 비트의 idx 찾기

int n = 6;  // 00000110
int idx = (n & -n);  // 00000110 & 11111010 == 00000010(2)
// 비트의 음수표현은 양수표현된 비트를 반전시킨 것에 1을 더하는 것이다.
// 부호비트가 1이면 음수, 0이면 양수
// -n == ~n + 1 == (1001 + 0001 = 1010)
// idx = 2

 

7. 크기가 n인 모든 집합의 모든 비트 켜기

int n = 3;
cout << (1 << n) - 1 << "\n";
// 1000 - 0001 = 0111

 

8. idx번째 비트 xor연산 하기(해당 비트가 0이라면 1, 1이라면 0으로 만들기) 

// 1번째 비트 xor연산
int n = 18; // 10010(18)
int idx = 1;
n ^= (1 << idx);
cout << n << '\n'; // 16

 

9. s에 모든 원소 채우기

s |= (1<<8) - 1;

- 1000 0000 - 1 = 1111 1111

 

10. s를 0으로 초기화

s = 0;

-  s => 00000000 00000000 00000000 00000000

 

<비트마스킹 심화: 경우의 수, 매개변수>

- 비트마스킹: boolean배열의 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색, 수정 등의 작업을 하는 것

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

#include <iostream>
using namespace std;
const int n = 4;
int main()
{
	string a[n] = { "사과", "딸기", "포도", "배" };
	for (int i = 0; i < (1 << n); i++)
	{
		string ret = "";
		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j))
			{
				ret += (a[j] + " ");
			}
		}
		cout << ret << '\n';
	}
	return 0;
}

/*

사과
딸기
사과 딸기
포도
사과 포도
딸기 포도
사과 딸기 포도
배
사과 배
딸기 배
사과 딸기 배
포도 배
사과 포도 배
딸기 포도 배
사과 딸기 포도 배
*/

 1) 사과 딸기 포도 배 -> 0000으로 표현해서 변수 i를 0000~1111(i < (1<<4))의 범위로 설정

 2) 변수 j는 0, 1, 2, 3을 기반으로 (1 << 0), (1 << 1) 등으로 해당 번째의 비트가 켜져있냐 켜져있지 않냐를 통해 집합 확인

 

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

// 사과라는 매개변수가 포함이 되어있고 이어서 사과 + 포도, 사과 + 배 이런식의 매개변수를 더하는 것을 구현
#include <iostream>
using namespace std;
const int n = 4;
string a[4] = { "사과", "딸기", "포도", "배" };
void go(int num) 
{
	string ret = "";
	for (int i = 0; i < 4; i++) 
	{
		if (num & (1 << i)) ret += a[i] + " ";
	}
	cout << ret << '\n';
	return;
}
int main() 
{
	for (int i = 1; i < n; i++) 
	{
		go(1 | (1 << i));
	}
	return 0;
}
/*
사과 딸기
사과 포도
사과 배
*/

 

저작자표시 (새창열림)