编程之美之二进制数中1的个数

2024-02-19 03:48

本文主要是介绍编程之美之二进制数中1的个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题:

对于一个字节(8bit)的变量,求其二进制中1的个数,要求算法的执行效率尽可能的高。

例如把9表示成二进制是1001,有2位是1,因此如果输入9,1的个数为2。


解法一:

可以举一个8位二进制的例子。对于二进制操纵,我们除以一个2,原来数字就会减少一个0(向右移一位)。如果除的过程中有余,那么久表示当前位置有一个1。

以10100010为例:

第一次除以2时,商为1010001,余为0

第二次除以2时,商为101000,余为1

因此,考虑利用整形数据除法的特点,通过相除和判断余数的值进行分析。

[cpp]  view plain copy
  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     while(a)  
  5.     {  
  6.          if(a % 2 == 1)  
  7.          {  
  8.               count++;    
  9.          }  
  10.          a = a / 2;  
  11.     }  
  12.     return count;  
  13. }  

解法二:位操作

使用位操作同样达到相除的目的。

使用与操作(&)来判断最后一位是不是1,判断完后向右移一位,继续判断。

可以把这个八位数与00000001进行与操作,如果结果为1则表示这个八位数最后一位为1,否则为0。

[cpp]  view plain copy
  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     while(a)  
  5.     {  
  6.          count += a & 0x01;  
  7.          a >>= 1;  
  8.     }  
  9.     return count;  
  10. }  

位操作要比除法取余操作效率要高许多。


解法三:

作者用到一个巧妙的方法,自己与自己减1相与,(例:10100010 & 10100001 = 10100000)从而到达消去最后一位1,通过统计循环次数达到计算1的个数的目的,这个方法减少了一定的循环次数。

具体解析看看原著。

[cpp]  view plain copy
  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     while(a)  
  5.     {  
  6.         a = a & (a-1);  
  7.         count++;  
  8.     }  
  9.     return count;  
  10. }  


解法四:分支操作

解法三的复杂度降到O(M). 其中M为1的个数。这效率已经足够高了。

如果还不满足,还有一种方法。既然才是一个8位的数据(0~255),可以直接0~255的情况罗列出来,使用分支操作,得到答案。

这个方法看似很直接,但是效率可能会比其他方法要低。具体情况具体分析。如果a = 0比较一次就会得到答案,但是a = 255比较255次才得到答案

[cpp]  view plain copy
  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     switch(a)  
  5.     {  
  6.         case 0x0:  
  7.              count = 0;  
  8.              break;  
  9.         case 0x1:  
  10.         case 0x2:  
  11.         case 0x4:  
  12.         case 0x8:  
  13.         case 0x10:  
  14.         case 0x20:  
  15.         case 0x40:  
  16.         case 0x80:  
  17.              count = 1;  
  18.              break;  
  19.         case 0x3:  
  20.         case 0x6:  
  21.         case 0xc:  
  22.         case 0x18:  
  23.         case 0x30:  
  24.         case 0x60:  
  25.         case 0xc0:  
  26.              count = 2;  
  27.              break;   
  28.         //.....  
  29.     }  
  30.     return count;  
  31. }  


解法五:查表法

直接把0~255相应1的个数直接存在数组中,采取以空间换取时间。

[cpp]  view plain copy
  1. int CountTable[256] =       
  2. {          
  3.          0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,  
  4.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  5.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  6.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  7.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  8.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  9.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  10.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  11.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  12.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  13.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  14.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  15.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  16.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  17.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  18.          4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8          
  19. };  
  20.   
  21. int Count(int a)  
  22. {  
  23.     return CountTable[a];  
  24. }  

这篇关于编程之美之二进制数中1的个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/723398

相关文章

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

C语言中的常见进制转换详解(从二进制到十六进制)

《C语言中的常见进制转换详解(从二进制到十六进制)》进制转换是计算机编程中的一个常见任务,特别是在处理低级别的数据操作时,C语言作为一门底层编程语言,在进制转换方面提供了灵活的操作方式,今天,我们将深... 目录1、进制基础2、C语言中的进制转换2.1 从十进制转换为其他进制十进制转二进制十进制转八进制十进

Python 异步编程 asyncio简介及基本用法

《Python异步编程asyncio简介及基本用法》asyncio是Python的一个库,用于编写并发代码,使用协程、任务和Futures来处理I/O密集型和高延迟操作,本文给大家介绍Python... 目录1、asyncio是什么IO密集型任务特征2、怎么用1、基本用法2、关键字 async1、async

Java并发编程之如何优雅关闭钩子Shutdown Hook

《Java并发编程之如何优雅关闭钩子ShutdownHook》这篇文章主要为大家详细介绍了Java如何实现优雅关闭钩子ShutdownHook,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 目录关闭钩子简介关闭钩子应用场景数据库连接实战演示使用关闭钩子的注意事项开源框架中的关闭钩子机制1.

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

如何将二进制文件流转化为MockMultipartFile文件

《如何将二进制文件流转化为MockMultipartFile文件》文章主要介绍了如何使用Spring框架中的MockMultipartFile类来模拟文件上传,并处理上传逻辑,包括获取二进制文件流、创... 目录一、名词解释及业务解释1.具体业务流程2.转换对象解释1. MockMultipartFile2