비트연산

비트 연산은 우선순위가 낮은 편이기 때문에 원하는 위치에 괄호를 작성하여 정확하게 계산할 수 있도록 하는게 중요하다.

C++에서 1은 부호있는 32비트 상수이기  때문에, 64비트를 사용할 때에는 1뒤에 ull을 붙여줘야 제대로 인식한다.

unsigned long long bit = (1ull<<40)-1; (O) -> 1099511627775

unsigned long long bit = (1<<40)-1; (X) -> 18446744073709551615

공집합( 모든 비트가 0)

unsigned int bit = 0;

꽉찬 집합(모든 비트가 1)

unsigned int bit = (1<<n) - 1;

사용할 비트 수만큼 왼쪽으로 시프트한 다음 1을 빼면 된다.

unsigned int bit = (1<<32) - 1; -> 1111 1111 1111 1111 1111 1111 1111 1111

기존 비트에서 원하는 비트의 위치를 1로 바꾸기

비트를 1로 바꿀 만큼 왼쪽으로 시프트 시킨 후 , or연산을 한다.

bit |= (1<<n);

특정 비트가 1인지 확인하기

if(bit & (1<<n)) -> 특정 비트가 1이면 1<<n 반환, 0이면 0 반환

기존 비트에서 원하는 비트의 위치를 0으로 바꾸기

bit &= ~(1<<n);

n번째 비트가 0이면 1로, 1이면 0으로 바꾸기

bit ^= (1<<n); -> xor 연산을 하면 가능하다.

비트에서 1의 개수 세기

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

처음 1인 비트 찾기

int first = ( bit & -bit);

2^n의 값이 반환된다.

즉 10진수 240 은 1111 0000로, 처음 1은 4번째 비트에서 나타난다. 그러면 위 식에 의해 2^4 = 16의 값을 가지게 된다.

처음 1인 비트를 0으로 바꾸기

bit &= (bit -1);

모든 부분집합 탐색

처음 시작은 모든 비트가 1로 채워져있어야 한다.

for (int subset = a; subset; subset = ((subset - 1) & a))
    {
        
    }

참고문헌: 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략