32bit의 (부호 없는)숫자가 할 수 있는 것을 생각해 보자. 하나는 0부터 4294967295까지의 수를 표현할 수 있다. 이것은 32비트 자료형 정수(int32_t)가 할 수 있는 일이다. 또 다른 일은 0부터 31까지의 숫자로 이루어진 "집합"을 표현할 수 있다는 것이다. 우리는 이 숫자를 집합으로 사용하는 것에 대해서 고찰해 보려고 한다.
집합의 비트 표기 방법
우리는 어떤 수를 이진수로 표현할 수 있다. 그러면, 20, 21, ..., 2n자리에 각각 0이나 1이라는 수가 있을 것이다. 2n의 자리가 1이면, n이라는 원소가 있는것이고, 만약 아니면 없는 것이다. 예를들면, 9는, 2진수로 표현하면 1001이고, 이것은 {0, 3}이라는 집합을 나타내는 것이다. 이 방법을 쓰면, 32비트 자료형 정수를, {0, 1, ..., 31}의 부분집합에 하나씩 대응 시킬 수 있다.
비트연산과 집합연산 표기
집합에서 가장 기본적인 연산은, 합집합, 교집합, 차집합, 여집합 등등일 것이다. 우리는 합집합, 교집합, 여집합이 각각 | (bitwise-or, 둘 중 하나라도 1이면, 결과도 1이다.), & (bitwise-and, 둘 다 1인 경우에만, 결과가 1이다.), ~ (bitwise-not, 결과의 0, 1이 바뀐다.) 로 표현됨을 알 수 있다.
그리고 어떤 숫자 n만 들어있는 집합은, 2n이 {n}에 대응되고, <<연산으로 만들 수 있다.
우리는 이것들을 조합해서여러가지의 결과들을 정리할 수 있다. (집합 A는 비트 a에 대응된다.)
이렇게 숫자를 비트로 표시하면 빠른 속도로 다양하게 사용할 수 있는 여러 특징들을 가진다. 예를들면, 어떤 배열의 모든 subset에 대해 연산을 하는 방법은 다음과 같다.
for(int i=0; i<(1<<n); ++i)
{
for(int j=0; j<n; ++j)
{
printf("{");
if(i&(1<<j))
printf("%d, ", j);
printf("}\n");
}
}
위 코드는, 모든 {0, 1, ..., n-1} 부분집합을 전부다 출력하는 코드이다. printf를 바꿔서, 추가적인 연산을 할 수 있도록 바꿀 수 있다.
그리고 여러가지 bit manipulation들이 있다. 비트연산을 가지고 재미있는 일들을 할 수 있다. 가장 마지막 비트를 뽑아내는 연산, 모든 크기 x인 집합들을 순회하는 방법 등등 여러가지 manipluation이 있다. 재밌는 hack들이 있는 링크와 자주 쓰는 핵들을 몇개 소개하고 글을 마치겠다.
//x의 가장 마지막 비트를 계산함
x&-x;
//v랑 크기가 같고, 사전순으로 다음에 오는 집합을 찾음
unsigned int t = (v | (v - 1)) + 1; w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
//x의 모든 부분집합을 순회함.
for(int i=0; i=(i-x)&x; )
//x의 모든 부분집합을 역순으로 순회함
for(int i=x; i>0; i=(i-1)&x)
//gcc내장함수 이용, x에 있는 비트의 갯수를 반환함
__builtin_popcount(x); //x가 long long type이면 __builtin_popcountll(x);
//gcc내장함수 이용, x의 앞에 있는 0의 갯수를 셈 (x의 가장 큰 원소 = log2(x) = 31-clz(x))
__builtin_clz(x);
//gcc내장함수 이용, x의 뒤에 있는 0의 갯수를 셈 (x의 가장 작은 원소를 가져 옴, x&-x는 1<<__builtin_ctz(x)과 같음)
__builtin_ctz(x);
다양한 비트연산에 관련된 것들이 들어 있는 링크: https://graphics.stanford.edu/~seander/bithacks.html