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


+ Recent posts