*중요: 궁금한건 댓글로 남겨주세요!*

int는 32개의 비트의 조합으로 표현된다.
signed int의 경우 첫 비트가 부호를 나타내어 $[-2^{31},2^{31})$의 정수를 표현하고,
unsigned int의 경우 첫 비트도 일반적인 비트로 사용되어 $[0,2^{32})$의 정수를 표현한다.

* 만약 10진수를 2진수로 출력하고 싶다면 cout << bitset<n>(m) 구문을 사용하면 된다.

int형 $x$와 $-x$ 사이에 어떤 관계가 있을까?
2의 보수 관계가 있다. 이는 합이 $2^k$꼴이 되는 관계를 말한다.
즉, $x$와 $-x$를 비트 전개 상태에서 더하면 ${\overbrace{10\cdots0}^{32}}_{(2)}$이 되어 맨 앞 비트가 날아가서 0이 된다.

예시 1) $0\cdots 01011_{(2)}$는 int형으로 $11$
예시 2) $10\cdots 01011_{(2)}$는 int형으로 $-2147483637$
예시 3) $1\cdots1_{(2)}$는 int형으로 $-1$

비트 연산

AND, OR, NOT

AND: a&b

예시) $1011_{(2)}\&1101_{(2)}=1001_{(2)}$

ex 1. $x\&1=1$일때 $x$의 특징은?
ex 2. $x\&(2^k-1)\neq 0$일때 $x$의 특징은?
ex 3. $x\&(x-1)=0$일때 $x$의 특징은?
ex 4. $x\&-x$의 특징은?
ex 5. 1비트 정수 $n+m$개를 다음과 같이 xor 시켰을 때, 결과값의 특징은? $\overbrace{0\&\cdots \&0}^n \&\overbrace{1\&\cdots \&1}^m$

OR: a|b

예시) $1010_{(2)}|1100_{(2)}=1110_{(2)}$

ex 1. 1비트 정수 $n+m$개를 다음과 같이 or 시켰을 때, 결과값의 특징은? $\overbrace{0|\cdots |0}^n |\overbrace{1|\cdots |1}^m$

NOT: ~a

예시) ~$1\cdots 10010_{(2)} = 0\cdots 01101_{(2)}$

ex 1. ~$x$와 $-x$의 관계는?

XOR, SHIFT, builtin function

XOR: a^b

예시) $1010_{(2)}$^$1100_{(2)}=1110_{(2)}$

ex 1. 1비트 정수 $n+m$개를 다음과 같이 xor 시켰을 때, 결과값의 특징은? $\overbrace{0\text{^} \cdots \text{^}0}^n \text{^}\overbrace{1\text{^}\cdots\text{^}1}^m$

SHIFT: a<<b, a>>b

예시) $1011_{(2)}<<3 = 1011000_{(2)},\ 1011_{(2)}>>3=1_{(2)}$

builtin function: __builtin_popcount(a), __builtin_clz(a), __builtin_ctz(a)

예시) $\mathrm{popcount}(1011_{(2)})=3, \mathrm{clz}(1011_{(2)})=28, \mathrm{ctz}(1010_{(2)})=1$

주의: $n\ge32$인 경우는 int64_t와 1LL, __builtin...ll 사용

ex 1. $\lfloor \log_2(x)\rfloor$를 builtin function으로 구하라.
ex 2. $2^k||x$일 때 $k$를 builtin function으로 구하라.

`int`형 정수를 2진수 형태로 출력

for (int k = 31; k >= 0; --k)
    cout << (x>>k&1);

집합

집합의 표현

정수 $x\in [-2^{31},2^{31})$와 정수 집합 $U=[0,32)$에 대해, $\displaystyle X:=\{k\in U|x\&2^k\neq 0\}$이다.
편의상 $f(x)=X$라고 표기하겠다. 또, $f^{-1}(X)=x$라 하자.

여러가지 집합

$f(0)=\varnothing$, $f(-1)=U$
$f(2^k)=\{k\}\ \forall k\in U$
$f(-2^{31})=\{31\}$
$f(1011_{(2)})=\{0,1,3\}$

집합의 연산

정수와 집합이 일종의 동형 사상을 이룬다. 아래의 연산들을 이용하면 임의의 원소의 존재를 조회, 추가 및 삭제할 수 있다.

$f(a\&b)=f(a)\cap f(b)$
$f(a|b)=f(a)\cup f(b)$
$f(a$^$b)=f(a)\cup f(b)- f(a)\cap f(b)$
$f($~$a)=f(a)^C$
$\mathrm{popcount}(a)=|f(a)|$

집합 순회

디버깅의 편의를 위해 집합의 모든 원소를 나열하여 출력하는 코드를 제공한다.

void all_elements(int x){
    if (!x) cerr << "(∅)\n";
    else {
        int k = __builtin_ctz(x);
        cerr << "{" << k; while (++k < 32) if (x>>k&1) cerr << ',' << k;
        cerr << "}\n";
    }
}

$[0,n)$의 모든 부분집합을 순회

$f(x)\subset f(y)\iff f(x)\cup (f(x)^C\cap f(y))=f(y)\iff x+($~$x\&y)=y\Rightarrow x\le y.$
이 성질 때문에 비트를 이용하는 알고리즘인 bitDP가 잘 작동한다.

for (int b = 0; b != 1<<n; ++b) {
    // Code...
}

$[0,n)$의 부분집합 중 원소가 $k$개인 것들을 순회

코드 1:

for (int b = 0; b != 1<<n; ++b) {
    if (__builtin_popcount(b) == k) {
        // Code...
    }
}

코드 2:

for (int x,y,b=(1<<k)-1; b < 1<<n;
     x=b&-b, y=b+x, b=((b&~y)/x>>1)|y) {
    // Code...
}

$(n,k)$	코드 1	코드 2
$(26,13)$	0.3초	0.2초
$(28,14)$	1초	0.6초
$(30,15)$	4.1초	2.4초
$(32,16)$	13초	9초

결론: 겉보기에는 $O(2^n)$과 $O(2^m)$의 차이이므로 코드-2가 훨씬 빠를 것 같지만, 코드-1은 간단한 연산만 사용하고, 코드-2는 나눗셈 연산과 배정문, 여러번의 비트 연산을 사용했기 때문에 시간 차이가 그렇게 크지 않다.
실험 코드:

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define el '\n'
using namespace std; using ll = long long;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int64_t n = 36, m = 18;
    double kitamasa_time = 0, pllk_time = 0;
    time_t s;
    int cnt = 1;
    int64_t count;
    REP(i,1,cnt)
    {
        s = time(NULL), count = 0;
        for (int64_t x, y, b = (1LL<<m)-1; b < 1LL<<n;
            x = b&-b, y = b+x, b = ((b&~y)/x>>1)|y) {
            // Code...
            count++;
        }
        kitamasa_time += time(NULL)-s;
        cout << count << el;
        s = time(NULL), count = 0;
        for (int64_t b = 0; b < 1LL<<n; ++b) {
            if (__builtin_popcountll(b) == m) {
                // Code...
                count++;
            }
        }
        pllk_time += time(NULL)-s;
        cout << count << el;
    }
    cout << "kitamasa: " << kitamasa_time/cnt << "s\n";
    cout << "pllk: "<< pllk_time/cnt << "s\n";
}
/*
(n,m)=(26,13)
  kitamasa: 0.2s
  pllk: 0.3s
(n,m)=(28,14)
  kitamasa: 0.6s
  pllk: 1s
(n,m)=(30,15)
  kitamasa: 2.4s
  pllk: 4.1s
(n,m)=(32,16)
  kitamasa: 9s
  pllk: 13s
*/

집합 $X$의 모든 부분집합을 순회

정순 순회

직관적인 이해는 힘들다. 우선 코드를 살펴보자.
코드:

int b = 0;
do {
    // Code...
} while ((b=(b-x)&x)!=0);

$b$값에 $x$의 보수를 지속적으로 추가 하면서도 $x$의 부분집합으로 강제시켰다.
즉, $b=(b+(\text{~}x)+1)\text{&}x$이다.
$~x$는 $X$에 대응되는 비트들만 꺼져있다.
여기에 $f(b)\in X$인 $b$를 더하게 되면, $X-f(b)$에 대응되는 비트들만 꺼져있다.
이때 남은 $1$을 더하게 되면, $X-f(b)$의 최소원소 대응비트의 하위비트들이 모두 켜져있었기 때문에, 보수 처리 되면서 최소원소 대응비트는 켜지고, 최소원소 대응비트의 하위비트는 모두 꺼지게 된다. 따라서 비트열의 사전순 순서로 순회가 된다.

역순 순회

다행히도 역순 순회의 코드는 훨씬 이해가 쉽다. $1$을 뺄 때마다 최소원소 대응비트는 꺼지고 최소원소 대응비트의 하위비트는 모두 켜지기 때문에 위와 같은 이유로 역순 순회가 된다.
코드:

int b = x;
do {
    // Code...
} while ((b=(b-1)&x)!=x);

모든 부분집합의 부분집합을 순회하는 시간 복잡도

아래의 코드는 독특한 시간 복잡도를 가진다.

for (int x = 0, b; x != 1<<n; ++x) {
    b = 0;
    do {
        // Code...
    } while ((b=(b-x)&x));
}

바깥 for문에서 돌리는 집합 $X$의 부분집합을 순회하는데 $2^{|X|}$번의 연산을 한다. 따라서 전체 시간 복잡도는 크기가 같은 집합들끼리 묶어서 계산하면,
$T(n)= \Theta(\binom n0 \cdot 2^0+\binom n1 \cdot 2^1+\cdots +\binom nn \cdot 2^n)=\Theta(\sum_{k=0}^n \binom nk \cdot 2^k)=\Theta((1+2)^n)=\Theta(3^n)$이다.
ex. Close Group

활용

bitset

bitset<5> a("1011"), b(3), c(0b101);
cout << a << ' ' << b << ' ' << c << '\n'; // 01011 00011 00101
cout << a[0] << ' ' << (a&b)[2] << ' ' << c.count() << '\n'; // 1 0 2

알고리즘

여기서 다룰 내용은 아니라 토픽만 던지고 간다.

에라토스테네스의 체
포함배제의 원리
펜윅 트리
bit DP / connected profile DP
SOS DP

연습문제

Jinhan's Note

저작자표시 비영리 동일조건

'알고리즘 설명 > 기타' 카테고리의 다른 글

실수 없는 계산기하(1) ★ (0)	2022.02.17
두 포인터 구현 바로잡기 ★ (0)	2022.02.01
LIS의 최적화 (6)	2021.02.02
트리의 지름을 구하는 방법 시각적으로 이해하기 (0)	2021.01.27
볼록껍질 (Convex Hull) (0)	2021.01.21