비트마스킹 (Bitmasking) - 정보를 비트에 함축해서 간단히 표현하기

(Leftmost부터 i번째 비트 - 0-indexing)

Read	bit & (1<<i)
Update (1로)	bit | (1 << i)
Update (0으로)	bit & (~1 << i)
반전, 토글 (XOR)	bit ^ (1 << i)

N lowest bit 모두 1로 ex) N = 5 → 0b11111	(1 << N) -1

간단히 말해, binary(0 혹은 1)의 집합으로 표현되는 특정 정보 상태를 비트 단위로 저장해서 사용하는 방법.

 

ex) 4 종류의 음식 A,B,C,D가 있을 때, 각 음식을 먹었는지 안먹었는지 각 상태를 나타내기

각 음식을 먹었으면 1, 안먹었으면 0으로 나타낼 수 있음. 4개의 음식의 비트 상태를 모아 숫자로 표현 가능

0000 -> 하나도 안 먹음; 값 0

0001 -> A먹음; 값 1

...

0101 -> A, C 먹음; 값 1+4 = 5

...

1111 -> A, B, C, D 먹음; 값 1+2+4+8 = 15

 

 

장점) 각 상태를 integer로 간단하게 나타낼 수 있다. 수정도 쉽다.

 

(오른쪽 기준) 3번째 비트를 1로 변경 : 1010 | (1 << 2)

3번째 비트를 0으로 변경 : 1110 & (~1 << 2) 혹은 1110 ^ (1 << 2)

 

+ XOR 사용해서 부분 반전도 가능 (1과 XOR 되는 부분은 반전됨)

ex) (왼쪽에서) 5번째부터 8번째 비트까지만 반전

11111010 ^ 00001111 = 11110101

https://ergate.tistory.com/entry/XOR-%EC%97%B0%EC%82%B0%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EB%B0%98%EC%A0%84-%EA%B8%B0%EB%B2%95

 

// N개 비트를 가지고 비트마스킹
int MAX = (1 << N) - 1; // 2^N - 1
for(int status = 0; status <= MAX; status++) {
    
    for(int i = 0; i < N; i++) {
        int bit = status & 1 << i; // 각 비트 상태 추출
        ...
    }
    ...
}

 

위 예시는 먹었냐/안먹었냐 2가지 상태만 한 가지 비트에 기록하지만, 여러 비트를 하나로 묶어서 생각해서 3개 이상의 상태를 기록하는 것도 가능

ex) 상태 A, B, C, D -> bit 2개 필요

00 : A

01 : B

10 : C

11 : D

만약 n개의 요소가 각각 4가지 상태 가질 수 있다면, 총 2n개 비트 필요할 것.

 

 

기타 Bit manipulation

// int to bit-representation
int n = 10;
vector<int> bits;
for (; num > 0; num >>= 1)
	bits.push_back(num & 1);
// Reversed; LSB on front, MSB on back

 

 

mygumi.tistory.com/361

비트마스크(BitMask) 는 무엇인가? :: 마이구미

[비트마스킹이 핵심인 문제]

BOJ4991 - 로봇청소기

blog.naver.com/PostView.nhn?blogId=uss425&logNo=222276594709&categoryNo=94&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=search

 

BOJ14442 - 벽 부수고 이동하기2

BOJ1194 - 달이 차오른다, 가자.

 

 

[간단한 활용으로 쉽게 풀리는 문제]

BOJ17471 - 게리맨더링

 

---

Bitset STL 자료구조

 

비트 단위의 정보 저장에 용이한 자료구조. 0과 1로 방문 처리하는 vector<bool> visited같은 느낌.

 

★★유용한 점 : 

to_string 함수를 쓰면 비트 그대로 문자열화 가능.

to_ulong / to_ullong 함수로 비트가 표현하는 값 가져오기 가능.

bitset<10> visited; // 0-indexing 따름
visited[1] = 1 // 혹은 visited.set(1, true); 2번째 비트 1로 변경
visited[4]; // 5번째 비트 값

 

www.crocus.co.kr/549

비트셋(Bitset) STL 사용 방법

 

사용 예 (visited 배열로 사용)

// 140 BOJ 17471 게리맨더링
// Check group's connectivity using BFS
bool connected(vi& group) {
    bitset<10> visited;
    visited.set(group[0]-1, true);
    queue<int> q; q.push(group[0]);

    while (!q.empty()) {
        int city = q.front(); q.pop();

        // 근처 도시 중, 아직 방문 안한, 같은 그룹의 도시 방문
        for (int neighbor : g[city]) {
            if (visited[neighbor-1] || !binary_search(all(group), neighbor)) continue;

            visited[neighbor-1] = 1;
            q.push(neighbor);
        }
    }
	
    // 방문하지 못한 그룹 내 다른 도시가 있으면 분리된 것; false
    for(int city : group) if (!visited[city-1]) return false;
    return true;
}

 

[활용 문제]

BOJ1052 물병

 

 

---

Bit 다루는 기타 스킬들

 

lowbit = x & (-x) 

: returns x's rightmost bit 1

https://www.quora.com/What-does-x-x-lowbit-do-in-C++

 

 

⭐️ XOR을 활용한 중복제거

https://florian.github.io/xor-trick/#:~:text=XOR%20on%20the%20same%20argument%3A%20x%20%5E%20x%20%3D%200&text=This%20time%20we%20have%20to,the%20first%20and%20last%20row.&text=Intuitively%2C%20this%20means%20that%20if,they%20cancel%20each%20other%20out.

x ^ 0 = x

x ^ x = 0

x ^ y = y ^ x

이걸 활용하면, a ^ b ^ c ^ a ^ b = c (XOR에서 중복으로 나타나는 값들은 그냥 없애도 됨) 

That XOR Trick.mhtml

3.22MB

활용 문제) LC E-389. Find the Difference (중복 제거하기)