Bit Calculation

bit count

usage

1. And

어떤 정수 x가 짝수인지 여부 확인 가능

x가 짝수일 때는 x & 1 = 0이고 홀수일 때는 x & 1 = 1
일반화 -> x가 $2^k$ 로 나누어떨어지는 경우는 $x \& (2^k - 1) = 0$

1. Shift

x « k 는 x 에 $2^k$ 를 곱하는 것과 같음, 반대로 x » k 는 x 에 $2^k$ 를 나누는 것과 같음

1. Mask

정수의 특정한 비트 하나에 접급할 수 있게 해줌

정수 x의 k번째 비트를 1로 바꾸기 -> x | (1 « k)
정수 x의 k번재 비트를 0로 바꾸기 -> x & ~(1 « k)
정수 x의 k번째 비트를 뒤집기 -> x ^ (1 « k)
정수 x의 가장 오른쪽의 비트 1을 0으로 바꾸기 -> x & (x - 1)
정수 x의 제일 오른쪽의 비트 1을 제외하고 모두 0으로 바꾸기 -> x & -x
정수 x의 마지막 비트 1 다음에 나오는 모든 비트 뒤집기 -> x | (x - 1)
양의 정수 x에 대해 x & (x - 1) = 0 이면 x는 2의 거듭제곱

1. g++ 기본 기능

• __builtin_clz(x): 비트 표현의 왼쪽에 연속해서 있는 비트 0의 개수
• __builtin_ctz(x): 비트 표현의 오른쪽에 연속해서 있는 비트 0의 개수
• __builtin_popcount(x): 비트 표현에서 비트 1의 개수
• __builtin_parity(x): 비트 표현에서 비트 1의 개수에 대한 패리티(짝수 또는 홀수)

present set

집합 {0,1,2, …, n-1}의 모든 부분집합을 n비트 정수로 표현 가능
각 원소마다 비트 한 개만큼의 메모리를 사용하고 집합에 대한 연산을 비트 연산을 이용하여 구현 가능

집합 {1,3,4,8} = 100011010

// 집합에 포함된 원소를 모두 출력하는 코드
for(int i = 0; i<32; i++){
    if(x & (1 << i))
        cout << i << " ";
}

연산	집합에 대한 연산	비트 연산
교집합	$a \cap b$	a & b
합집합	$a \cup b$	a | b
여집합	$\bar{a}$	~a
차집합	$a \smallsetminus b$	a & (~b)

// {0,1,2, ..., n-1}의 모든 부분집합 차례로 살펴보기
for(int b=0; b<(1<<n); b++){
    // 부분집합 b 처리
}

// 집합 x의 모든 부분집합 차례로 살펴보기
int b = 0;
do {
    // 부분집합 b 처리
} while(b = (b-x) & x)