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

时间:2022-08-06 20:55:45

  原题:一个正整数,转成二进制后,这个二进制数包含多少个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的个数,可见该算法之妙。