面试题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图     参与者 这个模式涉及的 ...
一周排行
  • newInstance()和new() 在Java开发特别是数据库开发中,经常会用到Class.forName( )这个方法.通过查询Java Documentation我们会发现使用Class.forName( ) ...
  • 0. 环境说明:Ubuntu 14.04, MongoDB2.6.1 1.导入MongoDB中public Key值到Ubuntu包系统中 2. 在Sources列表中创建MongoDB的文件 3. 重新加载本地的文 ...
  • 首先:Origin软件已经是科研院所等单位的必备工作软件之一,之所以大家讨论得较少,有可能并不是其上手难度低,而是这些使用人群的学习理解能力要相对高一点吧: 其次:Excel不垃圾,但在函数绘图方面,比起Origin ...
  • 易网科技讯 北京时间10月31日消息,据国外媒体报道,夏普刚刚发布季度财报,在截至9月30日第二财季取得136亿日元(合1.39亿美元)净利润,这也是夏普两年来首次发布实现盈利的季度财报.今年第二财季夏普净利润为13 ...
  • * 工会系统开发: 3月28到4月20 28:基本整体软件结构开发完成. 29:开发 独立部分的功能,自定义alert UI,进度条定时器等内容,自定义邀请界面弹窗. 4: 菊花提示框,内容改编,主页的侧栏变化,已经 ...
  • 倒计时按钮效果 @implementationCountButton { UIColor *normal_bgColor; UIColor *enabled_bgColor; NSTimer *timer; NSIn ...
  • BI从业这些年,遇到过狠多不同的业务系统.经常会有朋友问我说,业务系统应该提交给BI系统中什么样的数据.这类问题总是需要自己反过来问自己的问题,比如如何根据一个日期计算是当年的第几周,还有为什么报表上的数字不准确等等 ...
  • 当你在手机上打开一家银行网站界面,很有可能该界面已被“偷梁换柱”,随后你的资金就面临被盗取的风险.昨日,百度手机卫士与易观智库联合发布<中国手机安全市场现状研究报告>,称移动支付风险成为用户最担心的威胁. ...
  • 今天小编为大家带来了全民枪战手雷属性详解 各种手雷伤害属性介绍,感兴趣的朋友们可以跟着小编去下文了解一下哦 今天小编为大家带来了全民枪战手雷属性详解 各种手雷伤害属性介绍,感兴趣的朋友们可以跟着小编去下文了解一下哦! ...
  • 给出一个图,求它是不是树.. 首先,一个图如果是树那么边数就是点数-1,然后再判断所有点是否连通.这里可以用并查集搞一下. 代码如下: #include<cstdio> #include<cstri ...