Bitmasking(비트마스킹) 알고리즘

비트연산자 활용법

 

아래에 기록하는 비트연산자 활용법은 모두 암기해야 한다.

비트 연산	코드
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. idx번째 비트 끄기

---

idx번째 비트끄기

S &= -(1 << idx)

 

예를 들어, S = 101010(18)에서 10010 빨간 부분의 1을 0으로 변경하고 싶으면?

그럼 1번째 비트이다.

 

먼저 000010을 만든다. (← [1 << 1]을 하면 만들 수 있다.)

그 다음 비트를 뒤집어준다.

→ 111101로 만들어진다.

 

여기서 S = 101010과 AND(&) 연산을 수행한다.

결과는 101000으로 만들어진다.

 

#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. idx번째 비트 XOR 연산(0은 1로, 1은 0으로)

---

idx번째 비트 XOR 연산

S ^= (1 << idx)

 

이건 컴퓨터 구성에서 배웠던 내용으로 간단한 내용이다.

XOR 연산은 두 수가 모두 0 또는 1일 때 0을 반환한다.

즉, 두 수가 다를 경우에는 1을 반환한다.

 

따라서 우리가 바꾸고자 하는 자리에 1과 XOR연산을 취하게 되면 0은 1과 다르기 때문에 1이 되는 것이고, 1은 1과 같기 때문에 0으로 변환하는 것이다.

 

#include <bits/stdc++.h>

using namespace std;

int main(){
    int S = 18;
    int idx = 1;
    
    S ^= (1 << idx);
    
    cout << S <<'\n'; // 16
    
    return 0;
}

 

 

 

 

 

 

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

---

최하위 켜져있는 비트 찾기

idx.= (S & -S)

 

2의 보수 개념이 등장하기 때문에 알아두어야 한다.

 

S = 10010이라고 가정한다.

-S = -(S + 1)이기 때문에

01101 + 1 = -S이다.

-S = 01110이며

 

10010

    &

01110

 

= 00010이 반환된다.

 

 

#include <bits/stdc++.h>

using namespace std;

int main(){
    int S = 18;
    int idx = (S & -S);
    
    cout << idx <<'\n';
    
    return 0;
}

 

 

 

 

 

 

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

---

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

(1 << n) - 1

 

이진수 / 비트연산자 / 비트마스킹을 배우는 이유는 이러한 비트들을 하나의 배열처럼 쓰기 위함이다.

 

예를 들어,

1111은

"0번째, 1번째, 2번째, 3번째 요소가 "포함"되어 있다"라고 표현할 수 있다.

 

배열 크기가 4인 boolean배열로 나타내는 것이 아닌 15라는 정수 하나로 나타낼 수 있기 때문에 메모리상 이득을 취할 수 있다.

 

만약, 위 [1, 1, 1, 1]에서 1번째는 포함하지 않는다면 [1, 1, 0, 1]로 나타낼 수 있다.

 

이를 비트연산자를 활용해서 표현해보자면

크기가 4라면 

16 (1 << 4)로 표현할 수 있고

(1 << 4) - 1을 하게 되면 15가 나온다.

 

15는 앞서 설명한 [1, 1, 1, 1]과 동일하다. 

이렇게 크기가 4인 집합을 하나의 숫자로 나타낸다면 (1 << n) -1로 나타내면 된다.

 

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n = 4;
    cout << (1 << n) - 1 << '\n'; // 15
    
    return 0;
}

 

 

 

 

 

 

 

#5. idx번째 비트를 켜기

---

idx번째 비트를 켜기

S |= (1 << idx)

 

10010(18)에서 0번째 비트를 켜면? 10011(19)가 된다.

 

이를 S |= (1 << idx)로 나타낼 수 있다.

 

|는 or을 나타낸다. 둘 중 하나라도 1을 나타내면 1로 변환할 수 있다.

따라서 바꾸고자 하는 S에 비트 켜기를 위한 자리수 (1 << idx)의 값과 or연산을 취하면 된다.

 

#include <bits/stdc++.h>

using namespace std;

int main(){
	int S = 18;
    int idx = 0;
    
    S |= (1 << idx);
    cout << S << '\n'; // 19
    
    return 0;
}

 

 

 

 

 

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

---

idx번째 비트가 켜져있는지 확인하기

if(S & (1 << idx))

 

이것은 너무나 쉽다. 비트가 켜져있어야 하는 것은 1을 의미하며 1을 얻기 위해서 AND연산을 취해 1일 때만 1이 출력되도록 구현하면 된다.

 

#include <bits/stdc++.h>

using namespace std;

int main(){
	int S = 18;
    int idx = 0;
    
    if(S & (1 << idx)){
        cout << "해당 idx : " << idx << "가 켜져있습니다.\n";
    } else{
        cout << "해당 idx : " << idx << "가 꺼져있습니다.\n";
    }
    
    return 0;
}

 

 

 

 

 

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

---

비트마스킹은 경우의 수를 표현하는데도 잘 쓰인다.

예를 들어, {사과, 딸기, 포도,, 배}의 모든 경우의 수는 어떻게 될까

 

{사과}

{딸기, 배}

{사과, 딸기, 포도}

...

 

이렇게 총 16가지가 나올 수 있다.

사과를 포함하거나 포함하지 않거나 해서 각각의 요소는 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 < (1 << n); i++){
        string ret = "";
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                ret += (a[j] + " ");
            }
        }
        cout << ret << '\n';
    }
    
    return 0;
}

 

이렇게 모든 집합을 표현할 수 있다.

i는 0000, 0001, 0010을 상징ㅎ한다.

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

 

즉, 이러한 것을 통해 4C1, 4C2, ... , 4C4 의 조합들의 모든 경우의 수를 한 번의 for문 만으로 표현이 가능한 것이다.

 

 

 

 

 

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

---

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

 

#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] + " ";
    }
    cout << ret << '\n';
    return;
}

int main(){
    for(int i=1;i<n;i++){
        go(1 | (1 << i));
    }
    
    return 0;
}