因為最近需要用到判斷某個數字是否是2的n次方，

這個方法應該是我在某本書上讀到的，

不過我手上應該是沒有哪本書。

方法其實是很簡單的，

某個數字是 X，

先將 X - 1 ，

再把 X ^ ( X - 1) 跟 X 比，

如果， X ^ ( X - 1 ) >= X，

就代表這個數字是2的n次方。

理由是因為，

假設 X = 1000000 （二進位)，

那麼 X - 1 = 0111111 (二進位)，

再來是 X ^ ( X - 1) = 1111111 ，

這個數字會大於等於原來的 X 。

而這是因為這個數字是2的n次方。

如果這個數字不是2的n次方，

假如 X = 1000100 ( 二進位）

而 X - 1 = 1000011 (二進位)

會讓 X ^ ( X - 1 ) = 111 （二進位）

最後的數字會小於 X 。

原因是在於最左邊的 1 ，

假如是2的n次方，整個數字（二進位）應該只會有一個1，

而不是2的n次方的話，就不只有一個1，

如果不是的話，這個會讓後面要做的 - 1 ，

在減掉 1 之後，最左邊的1還是不會改變。

因為最左邊的1還是存在，又跟原來的數字做 XOR ，

XOR 出來的結果，就會比原來的小。

這也是為什麼可以這樣判斷。

但是『等號』是只會成立在，當 X == 1 時。

而比較特別的是，當 X == 0 時，也是會成立的。

這可以當成是因為溢位的關係。

如果不想要這個特性的話，可以先檢查是否為0。

以下程式是用來驗證整個設計是否正確，

只有在條件(是否是2的n次方)成立時，才把 i 列印出來。

#include <stdio.h>

int main()
{
        unsigned int i = 0;
        for (i = 0;; i++) {
                if ((i ^ (i - 1)) >= i) {
                        printf("%08x\n", i);
                }
                if (i == 0xffffffff) {
                        break;
                }
        }
        return 0;
}