비트마스킹이란? |
비트마스킹 혹은 비트마스크라고 불리며 2진수를 이용하는 컴퓨터의 연산을 이용하여
비트(bit)연산을 통해서 집합에서 포함이 되는지/안되는지에 따라 생기는 부분집합들을 표현하는 방법론
비트마스크는 완전탐색에서 문제에서 나올수 있는 모든 경우의 수가
각각의 원소가 포함되거나 / 포함되지 않거나 두가지 선택으로 구성되는 경우 유용하게 사용됨
하지만 비트마스킹은 int형 숫자의 표기 가능비트에 한계가 있으므로 31개의 원소까지만가능하다는 한계가 있음(더 큰 자료형을 쓰면 상관없어지게 될 듯함)
| 기능 | 일반화된 함수 |
| idx번째 비트 켜기 | S |= (1 << idx) |
| dx번째 비트 끄기 | S &= ~(1 << idx) |
| idx번째 비트가 켜져 있는지 확인하기 | if(S & (1 << idx)) |
| idx번째 비트 XOR 연산 | S ^= (1 << idx) |
| 크기가 n인 집합의 모든 비트를 켜기 | (1 << n) - 1 |
| 최하위 켜져있는 비트 찾기 | idx = (S & -S) |
비트마스킹 사용 예시 |
원소가 5개인 집합의 모든 부분집합을 구하는 경우 어떤 집합의 부분집합은 각 원소가 해당 부분집합에 포함되거나 / 포함되지 않는 두가지 경우만 존재함
그러므로 5자리 이진수인 0 ~ 31을 이용해서 각 원소의 포함 여부를 체크 할 수 있음
비트 연산 |
1) 비트 연산의 종류
- AND 연산(&) : 둘 다 1이면 1
- OR 연산(|) : 둘 중 1개만 1이면 1
- NOT 연산(~) : 1이면 0으로, 0이면 1로
- XOR 연산(^) : 둘이 다르면 1, 같으면 0
- Shift 연산(<<, >>) : A << B라고 한다면 A를 좌측으로 B비트만큼 미는 것
| A | B | A & B | A | B | ~A | A ^ B |
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
※ 비트연산은 + - 연산보다 우선순위가 낮으므로 코딩할때는 헷갈리지 않게 ()로 감싸주기
- NOT 연산에 대한 작은 설명
음수를 구할때 2의 보수를 구한 후 1을 더하면 그게 음수인데
그 말인즉슨 -value = ~value + 1이므로 ~value = -(value + 1)이 됨
즉 ~27은 -28이다라고 바로 계산할 수 있음
2) 비트 연산 사용 예시
숫자 0과 1만 비트연산을 하는것이 아니라 모든 숫자에 사용 가능
모든 숫자는 2진수로 표현할 수 있으므로
13은 1101
72는 1001000
으로 표현 가능
만약 13과 72를 비트연산 한다면 자릿수를 맞춰주기 위해 13의 앞에 0을 붙여줘서
위처럼 사용 가능
3) NOT 연산 사용시 주의점
프로그래밍시 숫자들을 저장하는 자료형은 1가지가 아니며
예를들어 short, int, long, long long부터 signed/unsigned까지 다양하다
만약 16비트 자료형인 short의 경우 NOT연산을 수행하면 16자리의 수가 모두 바뀐다.
반면 32비트 자료형인 int의 경우 NOT연산을 수행하면 32자리의 수가 모두 바뀐다.
해당 결과를 10진수로 변환하면 결국 같은 값이 나오긴 하지만 2진수일때 둘의 값이 다르다는 점을 인지해야 함
- Short 형 40 NOT 연산 : -41, 2진수 출력 : 1111111111010111
- Integer 형 40 NOT 연산 : -41, 2진수 출력 : 11111111111111111111111111010111
4) Shift 연산
<<, >>로 표현하며 해당 방향으로 원본비트를 특정 값만큼 밀어버리는 개념
<< 연산
예를들어 1 << 3 이라고 한다면 1은 이진수로 1인데 이걸 좌측으로 3칸 밀어버리므로 1000이 된다.
7 << 3이라면 111이 3칸 밀리므로 111000이 된다.
일반화한다면 A << B라면 A에 2의 B승이 곱해지는 것
>> 연산
반면 >>는 우측으로 밀어버리는 것인데 우측으로 밀어서 밀려버리는 값들은 버려져서 그냥 삭제된다.
10 >> 2라면 10은 이진수로 1010인데 2칸 밀면 10이 된다.
일반화한다면 A >> B라면 A를 2의 B승만큼 나누는 것
즉 A / 2 == A >> 1이며 A * 2 == A << 1이다
5) 비트연산의 속도
비트연산의 시간복잡도는 내부적으로 O(1)의 상수시간이다.
하지만 프로그래밍시 IDE에서 최적화를 해주기 때문에 코딩할때 산술연산을 비트연산으로 할 필요는 없다
차이도 적고 유지보수에좋지 못하다
비트 연산으로 집합을 나타내는 법 |
1) 비트연산으로 부분집합 표현하기
비트마스크는 정수로 집합을 표현할 수 있음
예를들어 0 ~ 9의 숫자로 이루어진 정수 집합이 있을때
그 중 하나의 부분집합을 A라고 A = {1, 3, 4, 5, 9}라고 한다면 A = 570이라는 숫자로 나타낼 수 있음
왜냐하면, 부분집합에 포함되는 비트는 1로, 포함되지 않는 비트는 0으로 표현할 수 있기 때문
| 숫자 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 비트 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
위 비트를 이진수로 본다면 1000111010이 되므로 10진수로 바꾸면 570이 된다.
즉, 비트마스크를 이용하면 집합/부분집합을 정수로 나타낼 수 있다.
이렇게 집합을 정수로 나타내면 저장공간을 절약할 수 있고, index로도 활용이 가능한 장점이 있다
주의점은 인덱스와 마찬가지로 0부터 시작하게 활용해야 공간절약이 가능하므로
1~9의 숫자로 이루어진 집합이라고 하더라도 코드에서 i - 1처럼 코딩해서 0~8의 칸을 쓰게 만들어야 한다.
만약 0번칸을 버리게 되면 공간이 2배로 필요하게 되고 시간도 2배로 필요하게 됨
비트마스킹 자유자재로 하려면 아래 표를 외워버리는게 좋지 않을까...
| 기능 | 일반화된 함수 |
| idx번째 비트 켜기 | S |= (1 << idx) |
| dx번째 비트 끄기 | S &= ~(1 << idx) |
| idx번째 비트가 켜져 있는지 확인하기 | if(S & (1 << idx)) |
| idx번째 비트 XOR 연산 | S ^= (1 << idx) |
| 크기가 n인 집합의 모든 비트를 켜기 | (1 << n) - 1 |
| 최하위 켜져있는 비트 찾기 | idx = (S & -S) |
// 비트 끄기 예시코드
#include <bits/stdc++.h>
using namespace std;
int main() {
int S = 18;
int idx = 1;
S &= ~(1 << idx);
cout << S << '\n'; // 16
return 0;
}
2) 숫자가 부분집합에 포함되어있는지 확인하기(마스킹 하는 법)
0 ~ 9의 숫자 중 해당 숫자가 현재 집합에 포함되어 있는지 알아보는 방법
{1, 3, 4, 5, 9} = 570이라고 할 떄, 0이 해당 집합에 포함되어 있는지 확인하고 싶다면
0000000001과 AND(&)연산을 하면 0이 포함되어 있는지 아닌지 바로 알 수 있음
std::cout << 570 & (1 << 0);
// 이진수 1과 마스킹하므로 부분집합에 0이 포함되어 있다면 이진수 1이, 없다면 이진수 0이 나옴
// 단 출력은 10진수로 되므로 1 or 0이 출력
std::cout << 570 & (1 << 1);
// 이진수 10과 마스킹하므로 부분집합에 1이 포함되어 있다면 이진수 10이, 없다면 이진수 00이 나옴
// 단 출력은 10진수로 되므로 2 or 0이 출력
std::cout << 570 & (1 << 2);
// 이진수 100과 마스킹하므로 부분집합에 2가 포함되어 있다면 이진수 100이, 없다면 이진수 000이 나옴
// 단 출력은 10진수로 되므로 4 or 0이 출력
3) 숫자를 부분집합에 추가하기
마스킹으로 숫자가 부분집합에 포함되어있는지 확인할 수도 있지만
비트연산을 이용해 부분집합에 숫자를 추가할 수도 있음
특정 숫자를 추가하기 위해서는 해당 비트를 1로 만들어야 하므로 OR연산을 사용
만약 A = {1, 3, 4, 5, 9} 부분집합 570에 부분원소로 2를 추가하고 싶다면
처럼 연산이 될것이고 값은 574가 된다.
std::cout << 570 | (1 << 2);
4) 숫자를 부분집합에서 제거하기
특정 숫자를 제거하기 위해서는 NOT연산과 AND연산을 같이 사용
NOT연산으로 제거하고자 하는 위치의 비트만 0으로 만들고 나머지는 1로 만든 상태에서 AND연산
만약 부분집합에서 4를 제거하고 싶다면
std::cout << 570 & ~(1 << 4);
// 4가 제거됨
5) 토글 연산하기
0과 1을 왔다갔다 하게 연산
만약 현재 있다면 없애고, 현재 없다면 있게 만든다면
std::cout << 570 ^ (1 << 4);
6) 전체집합, 공집합 표현하기
전체집합 : 모든 숫자가 1이라는 뜻으로 N개의 비트가 1이라는 뜻
공집합 : 모든 비트가 0이라는 뜻
전체집합은 비트가 0부터 시작하므로 좌측으로 N번 이동후 1을 빼면 된다.
전체집합 : (1 << N) - 1
공집합 : 0
출처
https://blog.naver.com/jhc9639/222310927725