비트마스킹

비트마스킹을 활용한 몇가지 트릭을 알아보자

BASIC

// i번째 비트 on
mask |= (1<<i);
// i번째 비트 off
mask &= ~(1<<i);
// n개의 1을 갖는 full set
mask = (1<<n) -1;
// i번째 비트가 1인가?
if (mask & (1<<i)) ?
// i번째 비트 toggle (1->0, 0->1)
mask ^= (1<<i);

오른쪽에 1만 남기기 (최소 원소 남기기)

LSB = (mask & -mask)

log2(LSB) -> 오른쪽에 있는 0의 개수

오른쪽 1만 지우기 (최소원소 지우기)

mask &= mask-1;

결과과 0이라면 2의 거듭제곱이겠다.

비트카운트 (1의 개수)

// 1. 브루트포스 O(64) (재귀로도 구현가능)
int bitCount(unsigned long long mask) {
	int ret = 0;
    while (mask) {
    	ret += mask%2;
        mask /=2;
    }
    return ret;
}
// O(1의 개수)
// 2. 최소 원소 지우기를 이용한 최적화
int bitCount(unsigned long long mask) {
	int ret = 0;
    while (mask) {
    	ret++;
        mask = mask & (mask-1);
    }
    return ret;
}

내장 함수가 있다면 내장함수를 사용하면 된다. 하드웨어적으로 최적화가 되어있어서 근본적으로 더 빠르다.

모든 부분 집합 순회

1. 집합이 full set인 경우 (중간에 빈칸이 없음, 11111)

int full = (1<<n)-1;
for (int subset = 0; subset <= full; ++subset)

2. 집합이 sparse한 경우 (예 : 10010110101)

// 적당히 주어진 집합 full
int full;
for (int subset = full; subset>0; subset = (subset-1) & full)

2번이 잘 이해가 안된다면, full set인 경우를 대입해서 먼저 이해해보고 sparse set으로 확장해보자. 참고로 2번의 경우는 공집합을 포함하지 않는다. 이유는 subset = (subset-1) & full 에 있다. subset=0에 이 expression을 적용하면, 음수가 되어서 반복문이 끝나는게 우리의 바람이지만, -1의 2의 보수표현을 생각해보자. 따라서, 2번의 경우는 공집합을 따로 처리해 주어야 한다.