算法的强大——快速计算一个正二进制整数中包含多少个1-阿里云开发者社区

开发者社区> 橘子红了呐> 正文

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

简介:
+关注继续查看

原题:一个正整数,转成二进制后,这个二进制数包含多少个1?

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

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

  Private Function GetCount1OfValue(ByVal Value As IntegerAs 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 IntegerAs 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的个数,可见该算法之妙。

 

     

    本文转自万仓一黍博客园博客,原文链接:http://www.cnblogs.com/grenet/archive/2011/06/10/2077228.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
duilib 修复padding属性导致其他控件自动计算宽高度错误的bug和导致自己宽高度错误的bug
转载请说明原出处,谢谢~~:http://blog.csdn.net/zhuhongshu/article/details/42950733          BUG 一:padding导致其他控件宽度计算错误             今天在写项目的一个布局时,用到了最常用的相对布局属性padding:在一个纵向容器里,给其中的各个子元素设置了padding属性来做相对布局。
965 0
javascript 一个关于时间排序的算法(一个页面多个倒计时排序)
上周要做一个活动页面 秒杀列表页 需要一个时间的算法排序 自己琢磨了半天想了各种算法也没搞出来,后来问了下一个后台的php同学 他写了个算法给我看了下 ,刚开始看的时候觉得这就是个纯算法,不能转化成页面的dom效果,可是再看了两遍发现可以 于是我就改了改 实现了 不禁感叹 确实蛮赞的 于是就博一客;...
836 0
【算法导论】计数排序
计数排序 比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。 常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。
893 0
基于投票的热门计数算法策略
类似基于投票的热门计数算法普遍应用在热门文章,热门评论等场景中, 典型的比如网易和今日头条的评论区,国外比如Hacker News和Reddit的主题排序。
3325 0
Java数组排序基础算法,二维数组,排序时间计算,随机数产生
import java.util.Arrays; //包含Arrays import java.util.Random; public class HelloWorld { public static void main(String[] args){ // Scanner s = new Scanner(System.
818 0
学界 | 哈佛研究者推出新型优化算法,指数级提升计算速度
一种新出现的算法可以大大缩短电影推荐和出租车路径规划这类问题的计算时间。
971 0
3404
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载