문제 풀이를 위한 프로그래밍 기법 - 3. 비트 연산

이번 포스트에서는 비트연산에 대해 살펴보도록 하겠습니다.

프로그램에서 사용하는 n비트 정수는 내부적으로 n개의 비트로 구성된 이진수 형태로 저장이 됩니다.

예를 들어 32Bit int 자료형에서 42는 아래와 같습니다.

 

00000000000000000000000000101010

 

이진수를 10진수로 변경하는 방법은 각 자리 수에 2의 n-1제곱을 곱해주면 구할 수 있습니다.

(중학교 때 배운 것으로 간주하고 넘어가겠습니다.)

 

부호가 있는 n비트 정수 변수에는 -2^(n-1) 부터 2^(n-1)-1까지의 정수를 저장할 수 있습니다.

부호가 있는 정수 표현에서 가장 왼쪽 비트는 부호를 나타내며 0은 양수를 나타내고 1은 음수를 나타냅니다.

나머지 n-1개의 비트는 정수의 크기를 표현하게 됩니다.

 

부호가 없는 정수의 표현으로는 음이 아닌 양수만 표현할 수 있지만 대신 더 큰 수까지 표현이 가능합니다.

0부터 2^n - 1까지의 값을 가질 수 있습니다.

C++에서는 unsigned int형 변수가 이에 속하는데 0부터 2^32 - 1까지의 값을 가질 수 있습니다.

 

두 표현법 사이에는 나름의 관계가 있습니다. 부호가 있는 정수에서 -x는 부호가 없는 정수에서는 2^n - x와 같습니다.

즉, 부호가 있는 정수 x= -40은 부호가 없는 정수 y= 2^32 - 40과 같다는 것입니다.

 

비트 연산

비트 연산에는 And, Or, Xor, Not, Bit Shift, Bit Mask 등의 연산들이 있습니다. 하나씩 살펴보도록 하겠습니다.

 

AND 연산

공통으로 1이 들어간 위치에 1을 저장하는 연산입니다. x & y 라고 표현합니다.

 

OR 연산

둘 중 한 곳이라도 1이 있다면 해당 위치에 1을 저장하는 연산입니다. x | y 라고 표현합니다.

 

XOR 연산

두 값이 다른 경우에만 해당 위치에 1을 저장하는 연산입니다. x ^ y 라고 표현합니다.

1 ^ 1 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 0 ^ 0 = 0

 

NOT 연산

입력 값의 모든 비트를 뒤집어 놓는 연산입니다. ~x 라고 표현합니다.

~x = -x - 1 이라는 식이 성립합니다.

예를 들어 ~29 = -29 - 1 = -30입니다. 비트를 비교하면 아래와 같습니다.

 

~29 = 00000000000000000000000000011101

-30 = 11111111111111111111111111100010

 

비트 시프트 연산

비트 왼쪽 시프트 연산 x << k는 정수의 오른쪽에 비트 0을 k개 덧붙이는 연산이며 비트 오른쪽 시프트 연산 x >> k는 전수의 오른쪽 비트  k개를 제거하는 연산입니다.

즉, x << k는 x에 2^k(지수)를 곱하는 것과 같고 x >> k는 2^k(지수)를 나눈 후 정수로 내림한 것과 같습니다.

 

비트마스크

비트마스트 1 << k는 k번째 위치에만 비트 1이 있고 나머지 위치에는 비트 0이 있는 정수입니다.

따라서 비트마스크를 사용하면 정수의 특정한 비트 하나에 접근할 수 있습니다.

예를 들어 x & (1 << k)가 0이 아니라면, 이는 정수 x의 k번째 비트가 1이라는 의미입니다.

아래 코드는 int형 정수 x의 비트 표현을 출력하는 코드입니다.

for(int k = 31; k >= 0; k--) {
    if(x & (1 << k)) cout << "1";
    else cout << "0";
}
 

 

집합 표현하기

집합 {0, 1, 2, ..., n-1}의 모든 부분집합을 n비트 정수를 이용하여 표현할 수 있습니다.

이 때 정수의 비트 1은 그에 대응되는 원소가 부분집합에 속해 있음을 의미합니다.

예를 들어 int형 정수는 32Bit이므로 int형 변수로 집합 {0, 1, 2, ..., 31}의 모든 부분집합을 표현할 수 있습니다.

집합 {1, 3, 4, 8}의 비트 표현은 아래와 같습니다.

00000000000000000000000100011010

 

다음 코드는 {0, 1, 2, ..., n-1}의 부분집합을 표현하기 위한 int형 변수 x를 선언하고 원소 1, 3, 4, 8을 집합에 추가한 후, 집합의 크기를 출력하는 코드입니다.

int x = 0;
x |= (1<<1);
x |= (1<<3);
x |= (1<<4);
x |= (1<<8);
 
cout << __builtin_popcount(x) << "\n";

그리고 다음 코드는 집합에 포함된 원소를 모두 출력하는 코드입니다.

for(int i = 0; i < 32; i++) {
    if (x & (1 << i)) cout << i << " ";
}
// Output : 1 3 4 8

 

집합에 대한 연산

집합에 대한 연산은 크게 4가지가 있습니다.

교집합, 합집합, 여집합, 차집합

 

각 연산에 대한 비트 연산 표기 식은 다음과 같습니다.

교집합 : a & b

합집합 : a | b

여집합 : ~a

차집합 : a & (~b)

int x = (1 << 1) | (1 << 3) | (1 << 4) | (1 << 8);
int y = (1 << 3) | (1 << 6) | (1 << 8) | (1 << 9);
 
int z = x | y;
cout << __builtin_popcount(z) << "\n"; // 6

위 코드는 집합 1,3,4,8과 집합 3,6,8,9를 만든 후 합집합을 만드는 코드입니다.

비트 OR 연산을 통해 간단하게 구한 것을 알 수 있습니다.

 

C++ 비트셋

C++ Standard Library에는 Bitset(비트셋)이라는 자료 구조를 제공합니다.

이는 원소가 0 또는 1인 배열과 같이 쓸 수 있습니다. 다음은 10개 원소로 구성된 비트셋을 활용하는 코드입니다.

bitset<10> s;
s[1] = 1;
s[3] = 1;
s[4] = 1;
s[7] = 1;
cout << s[4] << "\n"; // 1
cout << s[5] << "\n"; // 0

count라는 함수는 비트셋에 포함된 1의 개수를 Return해주는 함수이며 비트 연산을 비트셋에 대해서도 그대로 적용이 가능합니다.

 

 

참고로 알아두면 좋은 점

g++ 컴파일러가 제공하는 비트 수 셀 때 유용한 함수가 있습니다.

__builtin_clz(x)

-> 비트 표현의 왼쪽에 연속해서 있는 비트 0의 개수

 

__builtin_ctz(x)

-> 비트 표현의 오른쪽에 연속해서 있는 비트 0의 개수

 

__builtin_popcount(x)

-> 비트 표현에서 1의 개수

 

__builtin_parity(x)

-> 비트 표현에서 비트 1의 개수에 대한 패리티(짝수 or 홀수)