判断一个整数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是否成立，是可行的。