Bitmasks

www.secmem.org/blog/2019/10/19/handy-function-about-bit/

 

1. 비트마스크 S의 가장 마지막 켜져있는 비트 (LSB)

펜윅 트리에 구현에 자주 이용되는 테크닉이다.

int lsb=mask&-mask;

 

2. 비트마스크 S의 부분집합(submask) 모두 순회

$O(2^N)$에 현재 주어진 비트마스크의 모든 부분집합들을 정확히 한번씩만 순회할 수 있다.

for(int i=mask; ; i=mask&(i-1))
{
	if(i==0) break;
}

 

3. 모든 가능한 비트마스크 S에 대해, S의 부분집합(submask) 모두 순회

모든 $O(2^N)$개의 비트마스크를 모두 순회하며, 각 비트마스크에 대해 부분집합을 모두 순회하는데 드는 시간은 $O(3^N)$이다.

S에 포함되지 않는 비트 / S에는 포함되지만 S의 부분집합에는 포함되지 않는 비트 / S의 부분집합에도 포함되는 비트 의 3가지 경우의 수가 있으므로 전체 시간 복잡도는 $O(3^N)$이다.

다른 분석방법으로는, $\sum_{k=0}^n {n \choose k}2^k =3^n$로, 이항정리를 이용할 수 있다.

 

4. SOS (Sum Of Subsets) DP

$f(mask)=\sum_{s\subseteq mask}A_s$의 형식으로 정의된 식을 $O(N2^N)$에 계산할 수 있다.

다음과 같은 dp를 정의한다.

$dp(mask, i)=$ mask의 부분집합들 중 오직 0~i번째 비트만 mask와 다름이 허용되는 집합들에 대한 합

위와 같이 정의한 이유는 기본적으로 mask에서 시작해서 최상위 비트부터 시작하여 낮은 비트쪽으로 가며 mask에도 그 비트가 켜져 있으면 꺼보는 형식으로 전이가 이루이지기 때문이다.

mask의 i번째 비트가 켜져 있다면 $dp(mask, i)=dp(mask, i-1)+dp(mask \oplus 2^i, i-1)$, 

mask의 i번째 비트가 꺼져 있다면 $dp(mask, i)=dp(mask, i-1)$ 의 점화식을 갖는다.