비트 마스크, 비트 마스킹, 2진법으로 바꾸기

~ 연산자 (Ones' Complement)

결과값은 수에 +1하고 -를 붙인 것과 같다.

~(3) 은 -4이다.

 

비트 연산 활용하기

k 번째 비트 끄기	mask &= ~(1 << k)
k 번째 비트 켜기	mask  |= (1 << k)
k 번째 비트가 켜졌는지 체크	mask & (1 << k)
k 번째 비트 XOR 연산	mask ^= (1 << k)
최하위 켜져있는 비트인덱스 k 찾기	k = ( mask & -mask )
크기가 n인 집합의 모든 비트 켜기	mask = (1 << n) - 1

 

 

비트 마스크는 모든 조합을 만들어낼 수 있다.

n이 정해져있다면 Combi로 풀어도 되고

몇 개를 뽑아야되는지 정해져 있지 않은 경우에는 비트마스크로 푸는게 더 효율적.

물론 비트마스크도 몇개가 마스킹 되어있는지 연산제외는 가능하지만.

for (int i = 1; i < (1 << n); ++i)

 

 

int 기준 30~31개의 조합에서만 사용가능하니 주의!!

 

예시문제 : 1285 동전 던지기

https://www.acmicpc.net/problem/1285

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// int main(void)
void Code::main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> bits(n);

    string str;
    for (int y = 0; y < n; ++y)
    {
        cin >> str;

        for (int x = 0; x < str.size(); ++x)
        {
            if (str[x] == 'T')
                bits[y] |= (1 << x);
        }
    }

    int ret = INT32_MAX;

    // 비트 조합
    for (int y = 0; y < (1 << n); ++y)
    {
        // 비트포함되어있다면 뒤집기
        for (int x = 0; x < n; ++x)
        {
            if (y & (1 << x))
                bits[x] = ~bits[x];
        }

        // 세로축 합 구하기
        int sum = 0;
        for (int k = 0; k < n; ++k)
        {
            int xSum = 0;
            for (const int& bit : bits)
            {
                if (bit & (1 << k))
                    ++xSum;
            }
            sum += min(xSum, n - xSum);
        }

        if (sum < ret)
            ret = sum;

        // 복구
        for (int x = 0; x < n; ++x)
        {
            if (y & (1 << x))
                bits[x] = ~bits[x];
        }
    }

    cout << ret;
}

 

 

10진법 수를 2진법으로 변환하기

16진법도 b만 바꾸면 동일하다.

int n = 100;
int b = 2;
vector<int> v;
while (n > 1)
{
    v.push_back(n % b);
    n /= b;
}
if (n == 1)
    v.push_back(1);

reverse(v.begin(), v.end());