面试题10_二进制中1的个数

题目描述:

请实现一个函数,输入一个整数,输出该整数中二进制表示中1的个数。

例如,把9表示成二进制是1001,有2位是1。因此,若输入9,输出2。


解题思路:

思路1、右移输入的整数n,判断最右边是否是1,若是,则计数加一,直到n为0,

这种思路对于正整数可行,但是对于负数,则会进入死循环。因为,负数右移,最高位补1 而不是0

因此,这种方法不可取。


思路2、左移数字1,首先将n与1进行与运算,判断最后一位是不是1,之后,将1左移一位,判断n的倒数第二位是不是1,直到1左移32位,为0,结束循环。(注意:这个32位是 32为系统 整型数占用的位数)


代码实现:

int NumberOf1(int n)
{
	int flag = 1;
	static unsigned int count = 0;
	while(flag)
	{
		if(n & flag)
			count++;
		flag = flag << 1;
	}
	
	return count;
}

思路3、

另外一种思路:

规律:把一整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0。

那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。


代码实现:

int NumberOf1(int n)
{
	static unsigned int count = 0;
	while(n)
	{
		count++;
		n = n&(n-1);
	}
	return count;
}



更多相关文章
  •     之前讨论过,在解决post跨域请求时,采用iframe+本域代理页的形式,兼容性(当然是包括IE6啦)是最好的.上次提到,代理页面的作用是:执行本域下的回调函数.就是这个原因,给XSS带来了便利.详细说明,请参考一个跨域请求的XSS漏洞     上次也提到,解决这个问题的根本在于杜绝不合法的 ...
  • MS15-035是Microsoft Graphics 组件处理增强型图元文件 (EMF) 的漏洞,可能允许远程执行代码. 通过补丁比对,可以看到主要是修补了一些可能存在整形溢出的位置,但是这些位置,我尝试了很多方法都无法执行到. 但是 int __thiscall MRSETDIBITSTODEV ...
  • 前些天用maven编译打包spark,搞得焦头烂额的,各种错误,层出不穷,想想也是醉了,于是乎,换种方式,使用sbt编译,看看人品如何! 首先,从官网spark官网下载spark源码包,解压出来.我这边使用的是1.4.0版本. 然后,我们需要把sbt配置好,配置很简单,无非就是SBT_HOME什么的 ...
  • 易网科技讯 8月24日消息,大唐电信科技股份有限公司今天公布的半年业绩显示,2012年上半年,大唐电信实现营业收入20.88亿元,与上年同期基本持平,净亏损3717.78万元,低于去年同期. 财报数据显示,大唐电信在今年上半年的主营业务毛利率比上年同期增加1.09个百分点,主营业务毛利总额比上年同期 ...
  • 在现在互联网盛行的时代,使得B/S架构飞速发展.曾经在大学的时候我一直都梦想着毕业后要找一个像腾讯这样大企业做C/S方面的开发工作(其实现在腾讯也有很多B/S软件),因为C/S体验度非常高,感觉非常好.但是此时此刻,我却没有这样的想法了.这是为什么呢?对于有经验的软件工程师都很清楚,B/S的程序部署 ...
  • 示例代码来自DoFactory.   概述 当你需要让对象返回之前的状态时,就使用备忘录模式.   意图 在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态.这样以后就可将该对象恢复到原先保存的状态.   UML   图1 备忘录模式的UML图     参与者 这个模式涉及的 ...
一周排行
  •   Bill Liu --如何让你的测试更敏捷ebay沈斌峰 --Mobile Automation TestingJason Woo -- Full Stack Testing   http://testerhom ...
  • IO的类型: 平均响应时间直接关联到具体的IO类型: 1. 读或写 2. 单块或多块         单块IO,指一次只读一个块.例如,当一个session等待一个单块IO时,典型的等待事件就是"db fi ...
  • 目录: 1) 从明源动力到创新工场这一路走来 2)解析ASP.NET WebForm和Mvc开发的区别 3)解析ASP.NET Mvc开发之查询数据实例 - ,既然学习EF,怎么可能不涉及到EF的延迟加载特性呢!那么 ...
  • 一.组播和网桥 1.一般的IP服务都是和底层的网卡设备没有关系的,完全由路由来决定,但是组播除外,因为组播需要将一个网卡显式的加入到一个组播组当中,一边该接口可以接收组播包,因此IP层和链路层就联系了起来. 2.使能 ...
  • 第一篇文章终于落笔了,本文将从思考的角度去重新认识一下Helloworld.在例子之后会提出不同的问题,引导大家去思考每一句乃至每个细节.同时希望能够让大家以后能够以不断思考不断提问的方式去看待自己的程序.我相信大家 ...
  • 晨报讯(记者 焦立坤)中兴通讯昨日宣布推出全新手机品牌"nubia",中文名"努比亚".这也是中兴首次在集团品牌之外发布新品牌,定位高端智能机.据介绍,中兴已为此建立单独团队独 ...
  • LAMP环境,项目运行错误日志路径:/var/log/httpd 错误日志例如: [Sat Jul 11 4 2015] [error] [client 192.168.17.3] PHP Warnin ...
  • [cpp]  /**总共是1024像素,递归建立4叉树,然后统计黑格子数量即可  *解决,我这里是模拟建立4叉树,能达到同样的效果,而且能  *节省一点时间和空间  */  www.2cto.com #include ...
  • 3-legged oauth resource owner, client, server. resource owner 给client访问权限去访问resource owner在server上的resource, ...
  • 在火狐下,复选框checkbox $('#checkbox').attr('checked',true); 不能勾选: 解决办法: $('#checkbox').get(0).checked=true;