비트마스크

PS에서 자주 쓰이는 기법인 비트마스크 정리

비트 연산자

• AND a & b
• OR a | b
• XOR a ^ b
• NOT ~a
• 정수 a를 왼쪽으로 b비트 시프트 a << b
• 정수 a를 오른쪽으로 b비트 시프트 a >> b

유의할 점

1. 비트 연산자의 연산자 우선순위는 == 등 비교 연산자보다 우선순위가 낮다. 따라서 다음과 같이 괄호를 꼭 붙여주자. bool ret = ((a & b) == 5);
2. 64비트 정수에서 비트 연산을 할 때 오버플로우가 발생하지 않도록 주의해야 한다. (1LL << 60)

비트 전부 채우기

int mask = (1 << N) - 1;

원소 추가하기

mask |= (1 << p);

원소의 포함 여부 확인하기

if (mask & (1 << p)) 비교 연산자를 사용하고자 하는 경우 ((mask & (1 << p)) == 0) 이렇게 괄호로 묶어주자.

원소 삭제하기

mask &= ~(1 << p); p번 비트를 제외하고 모두 켜져있는 숫자와 AND 연산

원소 토글

mask ^= (1 << p);

집합의 크기 구하기

int bitcount(int x) {
	if (x == 0) return 0;
	return x % 2 + bitcount(x / 2);
}

g++에서는 __builtin_popcount(mask)로 쉽게 구할 수 있다.

최하위 원소 구하기

g++에서는 __builtin_ctz(mask)로 최하위 원소의 위치를 쉽게 구할 수 있다. int m = (mask & -mask);로 위치 대신 비트를 직접 구할 수 있다. 2의 보수를 사용하는 시스템에서는, 음수를 표현하기 위해 비트를 뒤집고 그 결과에 1을 더하기 때문.

최하위 원소 지우기

mask &= (mask - 1);

모든 부분 집합 순회하기

for (int sub = mask; sub > 0; sub = (sub - 1) & mask)

$sub$에서 1을 빼면 켜져 있던 최하위 비트가 꺼지고, 그 밑에 있는 비트는 전부 켜진다. 이 결과와 $mask$의 AND 연산으로 모든 부분 집합을 방문할 수 있다.