x 보다 크거나 같은 가장 작은 2^n ?

양의 정수 $x$가 주어질 때, 이보다 크거나 같은 가장 작은 $a=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 도 추가로 해주어야 한다.