x & (x – 1)==0



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



算法的强大——快速计算一个正二进制整数中包含多少个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的个数,可见该算法之妙。