Hacker's Delight: 프로그래머의 필독서

 오해하면 안됀다. 해커가 그 해커가 아니다. ㅡ.ㅡ;;

 이 책은 비트연산의 모든것을 보여준다. 학부 2학년때 이 책을 처음

 접했는데 당시에는 나는 정말 신선한 충격을 받았었다.

 아마도 이책은 당신이 구현하기를 원하는 가장 효율적인 비트연산들의

 원리를 보여줄것이다.


 Hacker's Delight의 비트연산을 사용하는

 프로젝트 중 유명한것들의 예를 한번 들어보자.


 1. java jdk의 Integer 패키지


 2. Linux kernel


 3. apache lucene


 4. apache cassandra


 5. wnprolog

 리눅스 커널에도 이 저자의 소스가 들어있다는것에 주목하자.

 위의 리스트는 내가 아는것들만 적어놓은 것이므로 실제로는

 이보다 훨씬 많은 프로젝트에서 사용되었을 것이다.



 http://www.hackersdelight.org/HDcode.htm 이곳에 가면 친절하게

 직접 구현해 놓은 소스를 볼수 있다. 북마크해놓고 필요할때마다

 copy & paste를 사용하도록 하자. ㅡ.ㅡ;;;


 책 소개를 이정도로 끝내면 좀 싱거우니 많이 쓰는 코드를

 몇개 살펴보도록 하자.


 1. computing the number of 1-bits

 int pop(unsigned x) {

   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
   x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
   x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
   return x;
}

x의 전체 비트 수를 구하는 연산이다. 

소스의 첫라인을 보자. 0x5는 2진수로 0101이다. 

첫번째 라인을 거치게 되면 각각의 두비트에 대해서 카운팅한 값을 

합치게 된다. 마찬가지로 두번째 라인은 4비트의 카운팅한 값의 합을

구하게 된다. 최종적으로는 32비트의 카운팅 한값이 모두 합쳐지게 된다.

0xFF을 예로 들어보겠다. 

이진수로는 1111 1111이 된다. 

첫번째 라인(0x55555555)을 거치게 되면 

11 11 11 11 -> 01 01 01 01 + 01 01 01 01 = 10 10 10 10 

이 된다. 즉 두비트씩 살펴보면 두비트 단위로 카운팅한 값이 나온다. 

두번째 라인(0x33333333)을 거치게 되면 ( 4비트씩 살펴보자 )

1010 1010 -> 0010 0010 + 0010 0010 = 0100 0100 

이 된다. 즉 4비트씩 살펴보면 4비트 단위로 카운팅한 값이 나온다. 

이런식으로해서 최종적으로는 32비트 단위로 카운팅한 값이 나오게 된다. 

 2. round down to a power of 2

 unsigned flp2(unsigned x) {

   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x - (x >> 1);
}

2의 지수승으로의 버림 연산이다. 다시 말해서 주어진 x와 같거나 작은



2의 지수승을 구하는 연산이다. 



예를 들어, 



flp2(1) = 1 (2^0), flp2(2) = 2 (2^1), flp2(3) = 2 (2^1)



flp2(63) = 32 (2^5), flp2(64) = 64 (2^6) 



이 된다. 



코드를 간단히 설명하면 다음과 같다.



2의 지수승은 2진수로 다음과 같이 표현할수 있다.



십진수                        이진수
 1   ---------          0001
 2   ---------          0010
 4   ---------          0100
 8   ---------          1000
16  ---------        1 0000
32  ---------       10 0000




즉 1을 left shift하면 2의 지수값을 구할수 있다. 



따라서 2의 지수승으로 버림을 하려면 가장왼쪽(leftmost)에 있는 1비트만을



남기고 나머지를 모두 0으로 만들어버리면 된다. 




위의 코드에서 x | ( x >> 1) , x | (x >> 2) 등의 코드는 leftmost를 기준으로



오른쪽의 모든 비트를 1로 만든다. 



마지막 라인 x - ( x >> 1)에서 leftmost bit를 제외한 모든 비트가 0으로 반전



되고 leftmost bit만 남게되어 2의 지수승으로 버림연산이 되게 된다.




이외에도 부동소수점 나누셈, 64비트 나누셈, hilbert curve 생성, 



CRC-32등 주옥같은 코드들이 있다. 



프로그래머라면 한권 구매하여 책장에 꽂아두도록 하자.