n&(n-1)位运算的妙用_n与n-1-程序员宅基地

技术标签： n&(n-1)  数据结构与算法  位运算  

做oj遇到一道题，求二进制中1的个数。发现有大佬用来(n&n-1)。觉得很神奇。有空下来细想。确实是这么个道理。记录一下自己的分析过程

一、n-1发生了什么

①、二进制数n，n-1后，如果最后一位是0，将向前一位借2，2-1=1。最后一位为1。如果前一位为0，将继续向前一位借2，加上本身少掉的1.则变为1。一直遇到1。减为0.

所以 二进制 xxxx10000-1 = xxxx01111

②、n&n-1

按照上述 n=xxxx10000，n-1=xxxx01111

xxxx10000

xxxx01111

xxxx0000

可以看到将原来的最右边的1变为0了。

重复操作，有多少个1，这个操作就可以执行多少次。

贴上实现代码

#include <iostream>  
#include <cstdio>  
using namespace std;  
int main()  
{  
    int n, count = 0;  
    cin>>n;  
    while(n > 0)  
    {  
        count++;  
        n&=(n-1);  
    }  
    cout<<count<<endl;  
    return 0;  
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/nwpu_geeker/article/details/79763511

智能推荐

使用Taro开发鸿蒙原生应用——快速上手，鸿蒙应用开发指南_taro框架鸿蒙-程序员宅基地

文章浏览阅读1.3k次，点赞19次，收藏25次。在今年的敏捷团队建设中，我通过Suite执行器实现了一键自动化单元测试。Juint除了Suite执行器还有哪些执行器呢？由此我的Runner探索之旅开始了！随着鸿蒙系统的不断完善，许多应用厂商都希望将自己的应用移植到鸿蒙平台上。最近，Taro 发布了 v4.0.0-beta.x 版本，支持使用 Taro 快速开发鸿蒙原生应用，也可将现有的小程序转换为鸿蒙原生应用。本文将正式为开发者提供一份完整的鸿蒙应用开发指南，帮助大家使用 Taro 开发自己的第一个鸿蒙应用。_taro框架鸿蒙

Python重要数据结构之元组，命名元组(通俗易懂)-程序员宅基地

文章浏览阅读552次。元组元组和列表十分相似，大部分方法都通用，但是元组与列表的最大区别是列表可以修改，读取，删除，而元组创建之后则不能修改，不可以删除单个元素，但是可以删除整个元组。1. 定义元组元组在定义上和列表类似，定义元组时只需要用"(" 和 ")"把元素括起来就可以。执行结果如下：但是要注意，如果元组只有一个元素，则这个元素后面必须有“,”，否则元素就还是原来的类型。例如：执行结果如下：2. 删除元组由于元组不能修改，所以元组也不能单独删除部分元素，要删除只能删除整个元组。例如：结果如下_命名元组

springmvc接收json,使用@RequestBody_springmvc接收json数据一定要加上@requestbody-程序员宅基地

文章浏览阅读480次。springmvc可以直接接收表单参数或对象,使用@RequestParam或者默认不使用.接收json的话,使用@RequestBody,可以接收对象.或者使用map接收;需要在springmvc配置文件中添加如下配置; 并且前台如果用ajax传json对象的话,注意是json对象的字符串形式,可以用JSON.stringify()进行对象转字符串; &lt;!--支持..._springmvc接收json数据一定要加上@requestbody

蒲慕明：今人眼中的大脑之美 | 书评-程序员宅基地

文章浏览阅读214次。圣地亚哥·拉蒙-卡哈尔（Santiago Ramón y Cajal, 1852-1934）来源：知识分子撰文：蒲慕明现代神经科学起源于十九世纪末期；圣地亚哥·拉蒙-卡哈尔（Santi..._蒲慕明人怎么样

python 3.9啥时候出来_Python 3.9的到来到底是意味着什么？本文详细给你讲述！-程序员宅基地

文章浏览阅读38次。本文主要介绍Python3.9的一些新特性，如：更快速的进程释放，性能的提升，简便的新字符串函数，字典并集运算符以及更兼容稳定的内部API，详细如下：字典并集和可迭代更新字符串方法类型提示新的数学函数新的解析器IPv6范围内的地址新模块：区域信息其他语言更改1、字典并集和可迭代更新Python 3.9 dict类。如果有两个字典a和b，则现在可以使用这些运算符进行合并和更新。我们有合并运算符|：使..._python3.9.6什么时候发布的

【QT+QGIS跨平台编译】017：【zlib+Qt跨平台编译】（一套代码、一套框架，跨平台编译）-程序员宅基地

文章浏览阅读512次，点赞6次，收藏7次。通过一套zlib代码和框架，实现zlib跨平台编译。在Qt环境下，集成zlib库的头文件、库文件，构建跨平台编译的pro文件。通过构建的一套配置工程，基于Qt Creator IDE，完成跨平台编译实践。在Windows、Linux、MacOS等操作系统上进行测试，成功编译，形成的成果（头文件、库文件等）可在不同系统下调用或使用，从而更好地构建跨平台解决方案。采用的是zlib 1.2.12版本。读者可参考博客中的集成原理和pro文件，构建不同版本的zlib跨平台包。

随便推点

解析开关电源32个测试项：测试所需工具、测试方法、波形_元器件开短路测试项目-程序员宅基地

文章浏览阅读1.1k次。测试S.M.P.S. 在规格耐压和时间条件下, 是否产生电弧ARCING, 其CUT OFF CURRENT 是否满足SPEC. 要求, 及是否会对S.M.P.S.造成损伤.(1). 依SPEC.要求: 输入条件(RATED VOLTAGE), 输出负载(FULL LOAD) 和操作温度(OPERATION TEMP.),通常温度为:(0℃).(2). TRIGGER SLOPE 设定为"+", TRIGGER MODE 设定为"AUTO", TIME/DIV 视情况而定1S/DIV 或2S/DIV._元器件开短路测试项目

求解二阶偏微分方程c语言,科学网—求解偏微分方程开源有限元软件deal.II学习--Step 3 - 亓欣波的博文...-程序员宅基地

文章浏览阅读679次。完整版见：qixinbo.info.deal.II的程序结构deal.II采用面向对象编程，其中包含了很多的Modules，各自实现不同的功能，并有机地结合起来。如上图所示。具体为：TriangulationTriangulations是单元及其更低维度的边界的集合。triangulation存储了网格的几何和拓扑性质：单元怎样接触，它们的顶点在哪里。triangulation不知道将要在它上面使..._c语言二阶微分运算

turtlebot技术参数_turtlebot 加速度-程序员宅基地

文章浏览阅读1.9k次。turtlebot2的IMU只有陀螺仪，没有加速度计。但是还好有编码器提供里程计信息。它们的技术参数如下：（参考）1.陀螺仪Kobuki硬件入门教程-陀螺仪 说明： 介绍陀螺仪的相关信息 规范 3轴数字陀螺仪 制造商：STMicroelectronics 部件名称：L3G4200D 测量范围：±250度/秒 偏航轴在出厂时在±20度/秒至±100度/秒的范围内校准2.里程计（参考）M_turtlebot 加速度

探索未来网络: Gaio - 高性能、异步IO框架-程序员宅基地

文章浏览阅读347次，点赞3次，收藏10次。探索未来网络: Gaio - 高性能、异步IO框架项目地址:https://gitcode.com/xtaci/gaio项目简介GitCode上的Gaio 是一个由xtaci开发的基于Python的高性能、异步I/O框架。它的设计目标是提供一种简单而强大的方式，用于构建高效的网络应用，特别是在处理大量并发连接时。Gaio利用了Python 3.7及更高版本中的asyncio库，并采用了非阻塞...

Vue项目上线后关闭chroma的vue-devtools调试工具_devtools 调试模式,取消调试模式-程序员宅基地

文章浏览阅读247次。【代码】Vue项目上线后关闭chroma的vue-devtools调试工具。_devtools 调试模式,取消调试模式

JVM内存模型_gvm内存模型-程序员宅基地

文章浏览阅读1.8w次，点赞11次，收藏103次。Java在诞生之初就提出了"Write once，Run Anywhere"的口号，而这些都得益于JVM(Java Vritual Machine)，可以提前在不同的运行环境(linux或windows等)上安装JDK之后，就可以让同一份代码在任何地方运行了。而这里的JDK(Java Development Kit)是Java语言、Java虚拟机和Java类库的统称。一、JDK体系结构与Java跨平台特性1.1 JDK体系结构JDK是一个非常庞大的体系，里面包含了JVM、Java SE API(核心类_gvm内存模型

推荐文章

热门文章

相关标签