文档章节

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

一贱书生
 一贱书生
发布于 2016/11/18 15:20
字数 592
阅读 2
收藏 0
点赞 0
评论 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
博文 723
码字总数 600072
作品 0
面试算法知识梳理(14) - 数字算法

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

泽毛
2017/12/28
0
0
面试精选之位操作问题集锦

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

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

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

您这磨人的小妖精
2015/09/05
628
0
C位运算笔记(根据网上内容整理)1

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

cjs520
06/28
0
0
C位运算笔记(根据网上内容整理)1

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

cjs520
06/28
0
0
剑指Offer学习总结-二进制中1的个数

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

wwlcsdn000
01/17
0
0
补基础:自学:计算机科学导论 第二章 数字系统

2.2 位置化数字系统 在数字中符号所占据的位置决定了其表示的值。在该系统中,数字这样表示: +-(Sk-1 ……S2S1S0 ……S-l)b 它的值是: n = +-(Sk-1 bk-1 + …… + S1 b 1 + S0 b0 + S-1 b...

soulpei
06/26
0
0
Week 27 0918--0924

question 1:find happy number 答案1: 30% 循环将数的各位平方和相加,假如这个和为1就为真,否则继续循环,但是如果这个和出现过,将会陷入死循环,这时候返回False 这个答案比较慢,因为需...

vincehxb
2017/09/27
0
0
输入一个十进制整数,统计其中二进制1的个数

题目:统计给定的十进制数的二进制中1的个数 分析: 1.很多人看到这个需求的时候,第一反应是先把给定的十进制数转换成二进制数,再把二进制数转换为字符数组,再遍历这个字符数组计算1出现的...

kuangsonghan
2017/12/13
0
0
二进制中1的个数

这是一个经典的面试题,我们想知道一个二进制中1的个数,首先我们应该判断整数二进制表中最右边的一位是不是1,接着把输入的整数右移一位,此时原来处于右边倒数第二为被移到最右边了,再判断...

柠檬dream
2017/11/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式 Factory工厂模式 Singleton单例模式 Delegate委派模式 Strategy策略模式 Prototype原型模式 Template模板模式 Spring5 beans 接口实例化 代理Bean操作 ...

小致dad
14分钟前
0
0
SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
9
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
9
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
202
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部