[비트 마스킹][c++] 개념과 활용 방법에 대해서 알아보자

목차

 

비트연산자의 기본 사용

&	비트단위로 AND 연산을 한다.
|	비트단위로 OR 연산을 한다.
^	비트단위로 XOR 연산을 한다.
~	피연산자의 모든 비트를 반전시킨다.
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다.
>>	피연산자의 비트 열을 오른쪽으로 이동시킨다.

 

 

비트연산자의 활용 방법

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

 

 

idx번째 비트끄기

#include<iostream>
#include<algorithm>

using namespace std;



//idx번째 비트끄기
int main() {
    int S = 18;  //10010
                          
    int idx = 1;

    S &= ~(1 << idx);     // 00010 -> 11101

    cout << S << '\n';  //16  10000
   
    return 0;
}

 

idx번째 XOR 연산하기

#include<iostream>
#include<algorithm>

using namespace std;



//idx번째 XOR연산하기
int main() {
    int S = 18;  //10010
                          
    int idx = 1;

    S ^= (1 << idx);     //00010 

    cout << S << '\n';  //16  10000
   
    return 0;
}

 

 

최하위 켜져있는 비트 찾기

#include<iostream>
#include<algorithm>

using namespace std;



//최하위 켜져있는 비트 찾기
int main() {
    int S = 18;  //10010
                          
    int idx = (S & -S);  //01110

    cout << idx << '\n';  //2
   
    return 0;
}

 

 

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

#include<iostream>
#include<algorithm>

using namespace std;



//크기가 n인 집합의 모든 비트를 켜기
int main() {
    int n = 4;

    cout << (1 << n) - 1 << '\n'; //10000 -> 01111
    // 15
   
    return 0;
}

 

 

idx번째 비트를 켜기

#include<iostream>
#include<algorithm>

using namespace std;



//idx번째 비트 켜기
int main() {
    int S = 18;  //10010

    int idx = 0;

    S |= (1 << idx);     //00001

    cout << S << '\n';  //19  10011

    return 0;
}

 

 

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

#include<iostream>
#include<algorithm>

using namespace std;



//idx번째 비트가 켜져있는지 확인하기
int main() {
    int S = 18;  //10010

    int idx = 0;

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

 

 

비트 마스킹의 활용 이유

불리언 배열의 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색, 수정 등의 작업을 하기 위함

예)

101 -> {0, 2}

111 -> {0, 1, 2}

 

앞서 본 비트연산자를 통해 해당 요소가 포함 되어있는지 안되어 있는지 등을 쉽게 확인 가능

 

 

경우의 수에서 활용한 비트마스킹

#include<iostream>
#include<algorithm>

using namespace std;


const int n = 4;


//idx 번째 비트가 켜져있는지를 활용한 경우의 수
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;
}

 

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

#include<iostream>
#include<algorithm>

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 = 0; i < n; i++) {
        go(1 | (1 << i));
    }
    return 0;
}