面试题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图     参与者 这个模式涉及的 ...
一周排行
  • 0×1 简介 随着计算机犯罪个案数字不断上升和犯罪手段的数字化,搜集电子证据的工作成为提供重要线索及破案的关键.恢复已被破坏的计算机数据及提供相关的电子资料证据就是电子取证.NSTRT也曾协助进行过电子取证的工作,本 ...
  • 看到太多的各类系统整合ucenter出现的各种各样的问题,比如无法同步登入,同步退出,注册用户时候出现问题 研读过ucenter 的原理后,再结合测试 ucenter + modoer + discuz X 1.5 ...
  • 最近几年,随着UML(Unified Modeling Language,统一建模语言)的不断完善,其已被广泛运用于软件行业.掌握UML是每一个软件开发人提升自己能力的一个重要内容.下面,我想谈一谈我对UML学习的一 ...
  • 下面知识点都是从一些书本和其他博客吸取过来的.并无侵权的意思.......  1)根目录"/"     根目录位于目录结构的最顶层,用斜线(/)表示,类似于Windows操作系统的"C: ...
  • myeclipse里面导入新的项目 右键>import>General>existing...>next>select root >browse>项目>finish 导 ...
  • TCP/IP网络协议的通俗理解   前段时间做了一个开发,涉及到网络编程,开发过程比较顺利,但任务完成后始终觉得有一些疑惑.主要是因为对网络协议不太熟悉,对一些概念也没弄清楚.后来我花了一些时间去了解这些网络协议,现 ...
  • 升级向导这些语句不会自动升级,因此将标记有"(statement) is not supported"[(语句)不被支持] 的升级错误.例如,以下代码:a = VarPtr(b)升级后将变为: U ...
  • 现在是9,前三十分钟我还在公司里改着BUG,今天是我和其他人一起开发的功能发布的一天.但是bug不断的冒出来,哦,我先说一下,我做的看起来是偏后台,但是前台也有,比如修改功能,理论上说我直接向新增页面传递数据 ...
  • 易网科技讯 8月5日消息,据国外媒体报道,奥巴马政府日前对苹果部分产品在美国市场禁售令给予了否决,受此不利消息拖累,三星电子公司市值在周一因股价下跌而蒸发10亿美元.周一在首尔证券交易所,三星电子公司股价下跌0.9% ...
  • c# 中 is和as 操作符是用来进行强制类型转换的 is : 检查一个对象是否兼容于其他指定的类型,并返回一个Bool值,永远不会抛出异常object o = new object();   if (o is La ...