양의 정수 $x$가 주어질 때, 이보다 크거나 같은 가장 작은 $2^n$으로 표현되는 숫자를 찾아보자. 왜? FFT 때문이다. 물론, $\tt n = int(ceil(\log(double(x)) / \log(2.)))$로 계산하거나,
int a = 1;
while (a < x) a <<= 1; 로 찾을 수 있다;
$2^{n-1} < x \le 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 |
| Is Pow of 2 (0) | 2012.02.13 |
| Fixed-point RGB2Gray (0) | 2012.01.25 |
| Otsu-알고리즘의 새로운 해석 (0) | 2010.01.28 |
