Is Pow of 2

FFT를 적용할 때 이미지의 폭이나 높이가 2의 지수승으로 주어지는 경우가 가장 간단하다. 따라서 주어진 정수 x가 2의 지수 승인가 판별할 수 있는 방법이 필요하다. x가 양의 정수이고, 2^n으로 표현이 된다면, 2진수로 나타낼 때, (n+1) 번째 비트만 1이고 (0부터 센다), 나머지 비트는 모두 0이다. 그리고 x-1은  n 번째에서 0번째까지 모든 비트가 1이 된
다.  
    x                    x(2진수)            x-1
    1                      1                        0
    2                    10                         1
    4                   100                       11
    8                  1000                     111
     ................................................................
이 표를 보면, x와 x-1 사이에는 겹치는 비트가 없다. 따라서 두 수를 and 연산을 하면 0 이 되는 경우에는 2의 지수승이고, 그 이외의 경우에는 0이 아님을 알 수 있다. x = 2의 지수승  판별은    

                           return  x & (x - 1) == 0         /* x != 0 인 정수*/

인가를 보면 된다.

그런데 이 판별식은 x = 0 인 경우에는 성립이 안된다. x-1 = -1 이므로 32비트 자리 전부가 1로 채워지므로 x & (x-1) = 0 이어서 2의 지수승으로 판별한다. 따라서 0을 제외하는 방법을 찾아야 한다. (물론 함수 인자에서 양수로 제한을 하면 되지만 폼이 안 난다). 음수는 최상위 비트가 1로 채워진다는 사실을 이용하자. 최상위 비트를 1로 만들려면,

~0U                    =111111111111111..11111111(32개) 
~0U>>1              = 011111111111111..11111111
~(~0U>>1)          =100000000000000..00000000 
~(~0U>>1)|x       = x의 최상위 비트를 항상 1로 채워준다(음수 일 때는 자동으로 만족)
                             나머지 비트는 그대로 둔다.

따라서 이 값과 x-1을 and 연산을 하면 0 이하인 수가 들어오면 연산이 결과를 항상 0이 아니게 된다.

                          return  !((~(~0U>>1)|x) & (x - 1))          /*x = 정수 */    

0 하나를 예외 처리하기 위해서 너무 많은 과정을 거치는 것이 아닌가?