判断一个整数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个0，n>1）

　　　　　　X-1=11……1　　（n个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是否成立，是可行的。

算法的强大——快速计算一个正二进制整数中包含多少个1

　原题：一个正整数，转成二进制后，这个二进制数包含多少个1？

　　这个问题在网上看过多次，几番思考，也没有什么好的办法。采用最基本的办法，逐位判断，是1的统计加1，最后将统计数返回。

　　以下是这个思路的VB2008代码，不失一般性，将正整数的范围控制在（1~231-1）

　　Private Function GetCount1OfValue(ByVal Value As Integer) As Integer
　　　　Dim i As Integer, Count As Integer = 0
　　　　For i = 0 To 30
　　　　　　If (Value And 2 ^ i) = 2 ^ i Then Count += 1
　　　　Next
　　　　Return Count
　　End Function

　　但是近日，在网上发现一个很巧妙的算法，能够快速实现上述的计算功能。代码贴于下方

　　Private Function GetCount1OfValue(ByVal Value As Integer) As Integer　　

　　　　Dim Count As Integer = 0

　　　　Do While Value > 0

　　　　　　Value = Value And (Value - 1)

　　　　　　Count +=1

　　　　Loop

　　　　Return Count

　　End Function

　　这段代码的精髓就是在这一句：Value = Value And (Value - 1)

　　曾经用过类似语句的在我的博客“判断是否是2的N次方——证明x & (x - 1)==0的正确性”

　　那么这句语句到底起到什么作用呢？看下面的分析

　　假设Value=X1X2……Xn-1Xn，其中Xi(1≤i≤n)为1或0

　　不妨设Xi是最右边的1，那么Value就可以写成如下的形式

　　Value=X1X2……Xi-1Xi0……0，其中(1≤i≤n)，Xi后面有n-i个0

　　因为Xi=1，所以Value=X1X2……Xi-110……0，其中(1≤i≤n)，1后面有n-i个0

　　则Value-1=X1X2……Xi-101……1，其中(1≤i≤n)，0后面有n-i个1

　　则Value And (Value-1)=X1X2……Xi-100……0，其中(1≤i≤n)，Xi-1后面有n-i+1个0

　　因此，Value And (Value-1)的效果把最右边的1变成0

　　在上面的代码中，每把最右边的1变成0，则统计数加1，直到所有的1变成0为止。

　　这两个算法，第一个算法的循环次数是固定的，是31次，无论数值是多少（必须在范围之内）。而第二个算法和Value中的1的个数有关，循环的次数就是1的个数，可见该算法之妙。

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/8578999