判断一个整数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…&#x2……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是否成立，是可行的。
阅读(...) 评论()}