判斷一個整數x是否是2的N次方。
方法之一是判斷x & (x - 1)==0。若為True，則x是2的N次方；若為False，則x不是2的N次方。
有人質疑，他證明了“2的n次方一定符合這個條件”， 卻並沒有證明“符合這個條件的一定是2的n次方”呀！更沒有證明“不符合條件的一定不是2的n次方”呀。
現在，從兩個方面來證明這個方法的正確性
證明之前，先給出一些定義
&運算的定義：A & B 表示將A和B轉化為二進制，然後按照對位&運算。
例如：17 & 9
100012 =1710
& 1012 =910
------------------------
000012 =110
而對位&運算的定義如下：
1 & 1=1 ； 1 & 0=0 ； 0 & 1=0 ； 0 & 0=0
對位&運算還有如下性質：
A & 1=A ； A & 0=0 ； A & A=A ； A & B=B & A 此時：A，B=0或1
定義：
X=x1x2……xn-1xn，其中xi=1或0，1≤i≤n，n>0。顯然X>0（當X≤0，沒有討論的意義）
給定正整數X，X是2的N次方的充要條件是X轉化成二進制後，有且只能有一個1，其余的都是0
也就是說，若X是2的N次方，則x1=1，x2=……=xn-1=xn=0
若X不是2的N次方，則至少存在一個j，xj=1，1<j≤n
先證明“2的N次方符合X & (X - 1)==0條件”
當X=1時，1 & 0 =0，滿足條件
當X>1時，且X是2的N次方
如定義：X=100……0 （n-1個0，n>1）
X-1=11……1 （n-1個1，n>1）
則X & X-1是
100……02 =X10
& 11……12 =X-110
------------------------
00……02 =010
滿足條件
再證明“不是2的N次方不符合X & (X - 1)==0條件”
分兩種情況，
1、X是奇數，則X=x1x2……xn-1xn，x1=xn=1，故X=1x1x2……xn-11
則X-1=1x2……xn-10
則X & X-1是
1x2x3……xn-112 =X10
& 1x2x3……xn-102 =X-110
------------------------------------
1x2x3……xn-102 ≠010
不滿足X & (X - 1)==0的條件
2、X是偶數，則X=x1x2……xn-1xn，x1=1，xn=0
由於X不是2的N次方，因此x1，x2……xn-1中至少有兩個為1。設xj是最右邊的1
則X=1x2……xj-1xj0……0=1x2……xj-110……0 1<j<n，最右邊有n-j個0
則X-1=1x2……xj-101……1 1<j<n，最右邊有n-j個1
則X & X-1
1x2……xj-110……02 =X10
& 1x2……xj-101……12 =X-110
--------------------------------------
1x2……xj-100……02 ≠010
不滿足X & (X - 1)==0的條件
綜上所述，當X不是2的N次方的時候，是不滿足X & (X - 1)==0的條件的
因此，當X是2的N次方的時候X & (X - 1)==0成立，當X不是2的N次方的時候X & (X - 1)==0不成立。
故判斷X（X>0）是否是2的N次方的方法，判斷X & (X - 1)==0是否成立，是可行的。
