首页/新闻资讯/正文详情

二进制数1的计数算法与优化技巧详解

发布时间:2026/11/2 12:54:50 来源:云帆数科 栏目:资讯中心
二进制数1的计数算法与优化技巧详解
1. 二进制数1的计数问题解析在计算机科学和编程面试中计算一个二进制数中1的个数是一个经典的基础问题。这个问题看似简单却涉及到位运算、算法优化等多个核心概念。牛客网的每日一题经常出现这类题目因为它能很好地考察程序员对底层数据处理的掌握程度。我第一次遇到这个问题是在一次算法比赛中当时用了最直观的逐位检查方法结果在超大规模数据测试时遭遇了性能瓶颈。后来通过系统学习才发现这个简单问题背后藏着不少精妙的解法。2. 基础解法与性能分析2.1 逐位检查法最直接的想法是将数字转换为二进制字符串然后逐个字符统计1的数量。以数字13为例二进制1101def count_ones_naive(n): count 0 while n 0: count n % 2 n n 1 return count这个方法的时间复杂度是O(log n)因为需要检查每一位。虽然对小数字有效但当n很大时比如2^30循环次数会变得很多。注意右移操作(n 1)比除法(n // 2)效率更高这是位运算的一个小技巧。2.2 Brian Kernighan算法更高效的解法是利用n (n-1)这个位运算技巧它能将n的最低位的1变为0。例如n 13 (1101) n-1 12 (1100) n (n-1) 1101 1100 1100 (12) n 12 (1100) n-1 11 (1011) n (n-1) 1100 1011 1000 (8) n 8 (1000) n-1 7 (0111) n (n-1) 1000 0111 0000 (0)实现代码def count_ones_kernighan(n): count 0 while n ! 0: n n - 1 count 1 return count这个算法的时间复杂度是O(k)其中k是n中1的个数。对于稀疏的二进制数1的个数少性能提升明显。3. 进阶解法与硬件优化3.1 查表法预计算对于固定位数的数字比如32位整数可以预先计算所有可能值中1的个数存储在一个查找表中# 预计算8位数的1的个数 table [0] * 256 for i in range(256): table[i] (i 1) table[i 1] def count_ones_table(n): return (table[n 0xff] table[(n 8) 0xff] table[(n 16) 0xff] table[(n 24) 0xff])这种方法虽然需要额外的存储空间但查询时间是常数O(1)适合需要频繁调用的场景。3.2 并行计算法对于32位整数还可以使用并行计算的方法通过位运算同时计算多个位的1的个数def count_ones_parallel(n): n (n 0x55555555) ((n 1) 0x55555555) n (n 0x33333333) ((n 2) 0x33333333) n (n 0x0F0F0F0F) ((n 4) 0x0F0F0F0F) n (n 0x00FF00FF) ((n 8) 0x00FF00FF) n (n 0x0000FFFF) ((n 16) 0x0000FFFF) return n这个方法的原理是将32位数分成多个部分并行计算每部分的1的个数然后逐步合并结果。虽然代码看起来复杂但在现代CPU上执行效率很高。4. 实际应用与性能对比4.1 不同场景下的选择在实际编程中选择哪种方法取决于具体场景面试或教学推荐Brian Kernighan算法容易理解且效率不错高频调用查表法最佳牺牲空间换时间嵌入式系统并行计算法可能更适合减少内存访问一次性计算简单方法即可不必过度优化4.2 性能实测数据我测试了四种方法在计算0到1亿之间所有数字的1的总数时的表现Python 3.8方法时间(秒)相对速度逐位检查法45.21xBrian Kernighan12.73.6x查表法8.35.4x并行计算法6.17.4x注意实际性能会受编程语言、编译器优化等因素影响。在C/C中差异可能更大。5. 牛客网题目实战牛客网上常见的变种题目包括统计一个区间内所有数字的1的总数判断一个数是否是2的幂等价于1的个数是否为1找出两个数二进制表示不同的位数汉明距离以统计区间[1,n]内所有数字的1的总数为例最优解法不是逐个计算而是找数学规律def count_total_ones(n): count 0 i 1 while i n: divider i 1 count (n // divider) * i count max(0, (n % divider) - i 1) i 1 return count这个算法的时间复杂度是O(log n)比逐个计算O(n log n)快得多。6. 常见错误与调试技巧在实现这些算法时容易犯的错误包括负数处理Python的整数理论上无限大但其他语言如Java/C中右移负数可能导致无限循环解决方案使用无符号右移()或先将负数转换为补码边界条件输入为0或1时的特殊处理测试用例必须包含0、1、全1的数、2的幂等特殊情况运算符优先级位运算符的优先级容易混淆建议多用括号明确优先级如(n mask) ((n shift) mask)调试技巧打印二进制表示print(bin(n)[2:])单步调试观察位运算结果对小数字手动计算验证7. 扩展应用场景二进制1计数在多个领域有实际应用哈希算法设计计算哈希值的活跃位数图像处理计算二值图像的前景像素数密码学衡量密钥的随机性数据库位图索引的统计操作在机器学习中这个操作可以用于计算两个向量的汉明距离这在局部敏感哈希(LSH)等算法中很常见。8. 不同语言的实现差异虽然算法思想相同但不同语言的实现有细微差别Java/C:需要注意整数位数固定32/64位有符号数的右移行为不同可以使用内置函数如Integer.bitCount()Python:整数理论上无限大bin()函数方便查看二进制表示没有无符号右移操作JavaScript:所有数字都是64位浮点数位运算前会转换为32位整数可以使用Array.prototype.reduce实现9. 硬件层面的优化现代CPU通常有专门的指令来计算1的位数x86: POPCNT指令ARM: VCNT指令这些指令通常只需要1-2个时钟周期在C/C中可以通过编译器内置函数调用int __builtin_popcount(unsigned int x); // GCC int _mm_popcnt_u32(unsigned int x); // Intel intrinsicPython的第三方库如numpy也提供了优化实现import numpy as np np.unpackbits(np.array([n], dtypenp.uint8)).sum()10. 算法竞赛中的技巧在编程比赛中预处理常见操作的技巧预计算2^16以内所有数的1的个数然后分段统计对于大规模数据考虑数学公式而非逐个计算利用位运算并行处理多个数据一个典型例子是快速计算多个数的1的个数之和# 假设arr是数字列表 sum_table [bin(i).count(1) for i in range(256)] total sum(sum_table[x 0xff] sum_table[(x 8) 0xff] sum_table[(x 16) 0xff] sum_table[(x 24) 0xff] for x in arr)这种预处理查表的方法比逐个计算快很多特别是当arr很大时。

相关推荐

Jev 判断模型:只做判断不生成,本地部署与 AI 代理决策实践
Jev 判断模型:只做判断不生成,本地部署与 AI 代理决策实践

1. 从“只做判断、不说话”说起:Jev 到底是个什么定位第一次看到“Jev”这个名字,加上“只做判断、不说话”这个描述,我脑子里蹦出来的第一个念头是:这不就是把大语言模型里最容易被忽略的那一层单独拎出来了吗。我们平时用 AI&am… · 2026/11/2 12:53:50

MFC柱状图绘制原理:GDI资源管理与坐标映射校准
MFC柱状图绘制原理:GDI资源管理与坐标映射校准

简介:本资源是一份面向C初学者与MFC入门开发者的图形绘制实践项目,聚焦于使用MFC在单文档界面(SDI)中实现基于TXT数据驱动的柱状图可视化。核心围绕GDI绘图机制展开,重点演示CBrush画刷的创建、选入设备上下文及矩形填… · 2026/11/2 12:53:50

JavaScript作用域原理与实践指南
JavaScript作用域原理与实践指南

1. 为什么作用域是JavaScript的基石当我在2015年第一次接触JavaScript时,最困惑的就是为什么在函数内部定义的变量,外部无法访问。直到理解了作用域这个概念,才真正打开了JavaScript的大门。作用域就像是一个透明的玻璃罩,决定了你… · 2026/11/2 12:53:50

XSS靶场实战:7关黑盒环境通关技巧
XSS靶场实战:7关黑盒环境通关技巧

1. XSS靶场实战:黑盒环境下的7关通关攻略最近在xss1.ctf8.com上体验了他们的XSS黑盒靶场,这个靶场包含了7个不同难度的关卡,非常适合用来练习XSS漏洞的挖掘和利用技巧。作为一个安全爱好者,我花了几天时间通关了这个靶场&#xff… · 2026/11/3 4:28:48

SAP工艺路线(Routing)在制造业的核心应用与优化
SAP工艺路线(Routing)在制造业的核心应用与优化

1. SAP工艺路线(Routing)业务视角解析在制造业ERP系统中,工艺路线(Routing)就像产品的"烹饪食谱",它详细规定了从原材料到成品的每个加工步骤。作为SAP PP(生产计划)模块的核心主数据,Routing直接关联着BOM(物料清单)、工作中心、生… · 2026/11/3 4:28:48

JUnit+HSQLDB+JPA+Cobertura:DAO测试覆盖率实践
JUnit+HSQLDB+JPA+Cobertura:DAO测试覆盖率实践

1. 先把这套组合的分工捋清楚一个数据访问层的测试要想跑得起来,光有 JUnit 是不够的。你至少还要三样东西:一个能装下你实体关系的数据库、一层能把实体映射成 SQL 的持久化实现、一套能量出“我到底测了多少”的度量工具。Cobertura、JUnit、HSQLDB、J… · 2026/11/3 4:28:48

ArcGIS数据转换实战:SHP到CAD全流程指南
ArcGIS数据转换实战:SHP到CAD全流程指南

1. ArcGIS数据转换实战:从SHP到CAD的全链路操作指南在地理信息系统(GIS)和计算机辅助设计(CAD)交叉领域工作多年,我经常遇到需要将ArcGIS的SHP格式数据与CAD软件互转的需求。这种需求在国土规划、市政建设和… · 2026/11/3 4:28:48

MXM笔记本改装:从GTX到RTX的硬件升级指南
MXM笔记本改装:从GTX到RTX的硬件升级指南

1. 项目概述:一台被低估的MXM笔记本改装潜力这台17.3寸的MXM接口笔记本在二手市场以不到800元的价格被秒抢,背后隐藏着令人惊讶的硬件改装潜力。MXM(Mobile PCI Express Module)是笔记本显卡的模块化接口标准,通常用于… · 2026/11/3 4:28:48

时间复杂度实战指南:从CPU物理代价到工程决策
时间复杂度实战指南:从CPU物理代价到工程决策

1. 为什么“时间复杂度”不是数学考试,而是你写代码时的呼吸节奏刚接触算法的人,常把时间复杂度当成一道要背公式的数学题:O(1)是常数,O(n)是线性,O(n)是平方……然后在LeetCode上卡在第5题,看着别人3分钟A… · 2026/11/3 4:27:48

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 4:42:45

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 5:17:18

STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战
STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题
ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践
基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 4:42:45

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 5:17:18

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码