文档章节

统计整数二进制表示中1的个数

一贱书生
 一贱书生
发布于 2016/11/18 15:20
字数 592
阅读 3
收藏 0

解决这个问题第一想法肯定是一位一位的去判断,是1计数器+1,否则不操作,跳到下一位,十分容易,编程初学者就可以做得到!

 

于是很容易得到这样的程序:

 

int Sum1ByBin(int num)
{
	int sum = 0;
	while (num)
	{
		if(sum %2 ==1)
		{
			sum ++;
		}
		sum/=2;
	}
	return sum;
}


 

 


或者用牛逼的位运算:

 

int Sum1ByBin(int num)
{
	int sum = 0;
	while (num)
	{
		sum += num&1;
		num>>1;
	}
	return sum;
}

 

 

上面这两篇代码是用的同样的算法, 时间复杂度是二进制的位数,于是可以想一下,有没有只有与二进制中1的位数相关的算法呢?

可以考虑每次找到从最低位开始遇到的第一个1,计数器加1然后把它清零,然后继续找下一个1。方法就是n&(n-1),这个操作对比当前位高的位没有任何影响,

对低位完全清零。举个栗子吧!5。 5是101,第一次运算101&100 == 100,并且计数器加一,第二次运算100&011 == 0,计数器加一。循环结束啦!

所以5有2个1。牛逼吧! 看看代码是怎么实现的:

 

int Sum1byBin(int num)
{
	int sum = 0;
	while(num)
	{
		num &= num-1;
		sum++;
	}
	return 0;
}

很是简单,这就是位运算的好处,据说这个算法没把位运算发挥到极致,也没有得到这个算法最优解。

 

请读者先look一段代码,看看能不能看懂是什么功能:

 

int Sum1byBin(int num)
{
	num =	(num&0x55555555)	+	((num>>1)&0x55555555);
	num = (num&0x33333333)	+	((num>>2)&0x33333333);
	num	=	(num&0x0f0f0f0f)	+	((num>>4)&&0x0f0f0f0f);
	num	=	(num&0x00ff00ff)	+	((num>>4)&&0x00ff00ff);
	num	=	(num&0x0000ffff)	+	((num>>4)&&0x0000ffff);

	return num;
}

卧槽,这个是在玩什么中的制表符导致空格这么大的不怪我!

 

回想第一次遇到这个代码的时候我第一印象,这是什么**玩意,后来经过分析并且有高手帮助理解,这个功能正是利用了位运算,将一个数中二进制表中1 的个数算了出来。利用的是分治思想,先计算每对相邻的2位中有几个1,再计算相邻的4位有一个1 ,再计算相邻的8位、16位、32位有几个1,到此结束,32位的机器int就是32位,所以算

到32位就够啦!!!

 

 

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
面试精选之位操作问题集锦

Java 中位运算符有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>),只针对 int 类型有效,也可以作用于 byte、short、char、long,当为这四种类型时,J...

JohnnyShieh
2017/12/28
0
0
面试算法知识梳理(14) - 数字算法

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 面试算法知识梳理(2) - 字符串算法第一部分 面试算法知识梳理(3) - 字符串算法第二部分 面试算法知识梳理(4) - 数组第一部分 面试...

泽毛
2017/12/28
0
0
bitset bitmap 海量数据处理

bitmap:是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 适用范围...

您这磨人的小妖精
2015/09/05
628
0
剑指Offer学习总结-二进制中1的个数

剑指Offer学习总结-二进制中1的个数 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.16...

wwlcsdn000
2018/01/17
0
0
C位运算笔记(根据网上内容整理)1

什么是位运算? 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。由于位运算直接对内存数据进行操作,不需要转成十进制,...

cjs520
2018/06/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

图像库stb_image

https://github.com/nothings/stb 目前一般主流的图像格式也就是bmp,jpg,png,tga,dds,除了DDS一般是给DX用的,虽然一堆OpenGL程序也有用的,但是我一般只用png和tga, png不用说了,带a...

robslove
5分钟前
0
0
Spring 事务提交回滚源码解析

前言 在上篇文章 Spring 事务初始化源码分析 中分析了 Spring 事务初始化的一个过程,当初始化完成后,Spring 是如何去获取事务,当目标方法异常后,又是如何进行回滚的,又或是目标方法执行...

TSMYK
23分钟前
0
0
百度黄埔学院将培养一批首席AI架构师,为“国之重器”赋能

深度学习高端人才不仅是AI发展的重要养分,也是企业转型AI巨大推动力。2019年1月19日,百度黄埔学院——深度学习架构师培养计划在百度科技园举行开学典礼,深度学习技术及应用国家工程实验室...

深度学习之桨
50分钟前
2
0
扒站wget仿站

wget -c -r -p -np -k http://xxx.com/xxx 其中: -c, --continue (断点续传) 接着下载没下载完的文件 -r, --recursive(递归) specify recursive download.(指定递归下载) -p, --page...

临江仙卜算子
52分钟前
2
0
Nextjs+React非页面组件SSR渲染

@随风溜达的向日葵 Nextjs Nextjs是React生态中非常受欢迎的SSR(server side render——服务端渲染)框架,只需要几个步骤就可以搭建一个支持SSR的工程(_Nextjs_的快速搭建见Next.js入门)...

随风溜达的向日葵
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部