양의 정수  x가 주어질 때, 이보다 크거나 같은 가장 작은 2^n의 숫자를 찾아보자. 왜? FFT 때문이다. 물론,  n = (int)ceil(log(x) / log(2.)) 로 계산하거나, 
                    int a = 1;
                    while (a < x) a <<= 1; 
로 찾을 수 있다;

2^(n-1) < x <= 2^n 사이에 있으면, 원하는 답은 2^n이다. x=2^n 인 경우를 제외하고 모두 n번째 비트가 1로 세팅이 된다. 따라서, 통일시키기 위해서 1을 빼면, x-1 은 n 번째 비트가 항상 1로 주어진다.  이제, 남은 일은 n-1 번째에서 0번째까지 모든 비트를 1로 채우면 된다. 그 결과에 1을 더하면 원하는 2^n을 얻는다.  n-번째 비트가 1이고 이를 이용해서 하위비트를 채우기 위해서는 차례로 >> 연산을 한 후에 or 연산을 하면 된다.

a = x - 1
a                   = 1xxxxxxxxxxxxxxxxxxxxxxxx
a >> 1             = 01xxxxxxxxxxxxxxxxxxxxxxx
a >> 2             = 001xxxxxxxxxxxxxxxxxxxxxx 
.......

31번의 >> 연산을 한 후에 or 연산을 하면 n이하의 모든 비트가 1로 채워진다(31은 최대로의 경우다. 사전에 답을 모르므로 31번 >>까지 해야 한다). 이것은 너무 낭비다.  잘 살펴보면,

a | (a>>1) = 11xxxxxxxxxxxxxxxxxxxxxxxxx

형태이어서, 상위 두 자리 비트가 이미 세팅이 되어 있으므로, 이 결과를 다시  >> 2 하여서 이전 결과와 or연산을 하면 상위 4자리의 비트가가 채워지고, 또다시 이 결과를 >>4 하고 난 후에 직전 결과와 or 연산을 하면 상위 8자리의 비트가 1로 채워진다. 이런식으로 하면 >>16까지 하면 32자리를 모두 커버할 수 있다.

따라서, 전체적인 알고리즘은 (x > 0)
 

   x-- ; 
   x |= (x >> 1);  //상위 2 자리 채움
   x |= (x >> 2);  //상위 4자리
 채움 
   x |= (x >> 4);  //상위 8자리
 채움 
   x |= (x >> 8);  //상위 16자리
 채움 
   x |= (x >> 16);//상위 32자리
 채움 

   x++;
   return x;


단, 32비트 머신에서만이다. 64비트 프로그래밍에서는 >>32 도 추가로 해주어야 한다.

'Image Recognition > Fundamental' 카테고리의 다른 글

Ellipse Parameters  (0) 2012.10.13
float 타입 변수의 절대값은?  (0) 2012.02.17
x 보다 크거나 같은 가장 작은 2^n ?  (0) 2012.02.13
Is Pow of 2  (0) 2012.02.13
Fixed-point RGB2Gray  (0) 2012.01.25
A Fast 2D Otsu Thresholding Algorithm Based on Improved Histogram  (0) 2010.11.17
Posted by helloktk