기초 비트 연산

비트연산의 세계는 끝도 없지만, 기초적인 것부터 하나씩 보다보면 특성상 이해하지 못할 것도 없다. network flow를 모를지라도 비트연산은 계속 보다보면 적응이 되기 때문.

기초 Reminder

시작하기에 앞서, remind 차원에서 2진수 1011이 어떻게 10진수로 변환되는지를 상기해보자.

1	0	1	1
1 * 2^3	0 * 2^2	1 * 2^1	1 * 2^0
8	0	2	1

위 과정을 거쳐 1011은 11로 변환된다. 이 과정에서 볼 수 있는 것처럼, 만약 전체 셀이 좌측으로 1칸 이동하게 된다면, 이 수에 2를 곱한 것과 같은 결과를 낳는다는 것을 알 수 있다.

1	0	1	1	0
1 * 2^4	0 * 2^3	1 * 2^2	1 * 2^1	0 * 2^0
16	0	4	2	0

즉, 이 수는 11*2 = 22와 결과가 같아진다. 이를 코드로 구현해서 2의 제곱수를 곱하는 코드를 구현하면 아래처럼 된다.

int get2powermultiply(int v, int pow2) {
    return v << pow2;
}

또한, 맨 우측의 수만이 1을 나타내므로, 홀수일 경우에 맨 우측의 수는 항상 1이 됨도 덩달아 알 수 있다. 그래서, 홀수 판정 로직을 아래와 같이 짤 수 있다.

bool isOdd(int v) {
    return v & 1;
}

C++에서 1 = 0b00000...0001과 같다. 즉, & 연산을 취하면 LSB인 맨 최하위 비트만 남게 된다. 여기서 0b000..000과 같은 표기법을 잠깐 짚고 넘어가자.

C++에서의 2진수 표현

위에 잠깐 언급한 것처럼, C++에서는 2진수를 표현하기 위해 prefix인 0b를 붙인다. 이것을 붙임으로써 컴파일러한테 내가 앞으로 쓰는 숫자가 10진법이 아니라 2진법이라는 시그널을 주는 것이다. 유의할 점은, 이것이 자료형까지 초월하지는 않는다는 것이다. 흔히 쓰이는 32bit 시스템에서는 int 자료형 기준으로 32bit까지 사용할 수 있다. 그리고, 일반적으로 int는 부호있는 자료형 취급을 받기 때문에 그냥 int를 사용하게 되면 shift연산 등에서 조금 헷갈릴 수 있다. 그래서 가급적 비트연산을 할 경우에는 부호없는 자료형인 unsigned int를 사용하는 것을 추천한다.

또한, 고인물들은 2진수 표현으로 2진수를 쓰지 않는다. 무슨 말인가 하면, 아래와 같은 16진수를 쓰곤 한다는 것이다.

constexpr unsigned int flipbit = 0x55555555;

0x로 시작하는 경우 16진수를 뜻한다. 16진수는 16 = 2^4이므로, 2진수와 자리수별로 1:4 매핑이 된다. 0x5라고 쓴 것은, 0b0101을 의미한다. 0xF라고 쓴 것은 0b1111을 의미한다. 이렇게 고이게 되면, 그냥 16진수만 봐도 2진수를 보는 경지에 이른다. 이게 굳이 필요한 이유는? 2진수로 쓰면 매우 길어지는 것들이 간단하게 써지기 때문이다. 예를 몇가지 들면

0xFFFFFFFF = 0b11111111111111111111111111111111
0x55555555 = 0b01010101010101010101010101010101
0x33333333 = 0b00110011001100110011001100110011
0xAAAAAAAA = 0b10101010101010101010101010101010

와 같은 것들이 있다. 보이는대로 4자리가 하나로 묶이기 때문에, 표현이 길지 않고 간단하게 된다는 장점이 있다.

2의 보수

이 부분에 대한 언급을 스킵하면 뒤쪽에서 다루게 될 Tricky한 비트연산 방법들을 이해하기 어려워지기 때문에 짚고 넘어갈 필요가 있겠다.

작성 중

Tricky 한 비트 다루기

최하위 비트 끄기

흔히 팬윅 트리에서 많이 쓰이는 기법이다. 아래와 같이 호출하면, 맨 하위 1비트가 1 -> 0으로 바뀌게 된다.

v -= v & -v;

위에서 2의 보수 와 관련해 다룬 것과 연관이 있다. -v를 하는 순간 전체 비트가 반전되며, 1이 더해진다. 이와 & 연산을 하게되면, 맨 하위 비트를 제외하고는 모두 0이 됨을 알 수 있다.

그런데 위 방법 말고 operation 수가 더 적은 방식도 존재한다.

v = v & (v-1);

위 방식은 이진수 뺄셈의 특성을 이용한 방식으로, 1을 뺄 경우 최하위 1 비트가 0으로 바뀌고 그 아래 비트가 1로 바뀐다는 사실을 이용한다. 부호바꿈 연산을 절약할 수 있는 방식이다.