[剑指offer] 二进制中1的个数

题目描述

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路

如果一个整数不为0,那么这个整数至少有一位是1。如果我们把这个整数减1,那么原来处在整数最右边的1就会变为0,原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子:一个二进制数1100,从右边数起第三位是处于最右边的一个1。减去1后,第三位变成0,它后面的两位0变成了1,而前面的1保持不变,因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算,从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说,把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1,就可以进行多少次这样的操作。

来源于牛客网@菩提旭光

参考代码

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!=0){
            count += 1;
            n &= (n-1);
        }
        return count;
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/numberof1/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[LeetCode]1-bit and 2-bit Characters 1位和2位字符

链接:https://leetcode.com/problems/1-bit-and-2-bit-characters/description/ 难度:Eas...

1401
来自专栏前端迷

很实用的前端开发规范

1.标准变量命名使用驼峰式命名 eg. let thisIsMyName; 2.常量全部大写,并使用下划线连接 eg. const MAX_COUNT = 10...

1162
来自专栏逆向技术

框架原理第二讲,RTTI,运行时类型识别.(以MFC框架讲解)

           框架原理第二讲,RTTI,运行时类型识别.(以MFC框架讲解) 一丶什么是RTTI,以及RTTI怎么设计 通过第一讲,我们知道了怎么样升成...

21010
来自专栏软件开发 -- 分享 互助 成长

C++ STL之迭代器注意事项

1、两个迭代器组成的区间是前闭后开的 2、如果迭代器的有效性,如果迭代器所指向的元素已经被删除,那么迭代器会失效 http://blog.csdn.net/hs...

2335
来自专栏Pythonista

python中的函数

初中数学函数定义:一般的,在一个变化过程中,如果有两个变量x和y,并且对于x的每一个确定的值,y都有唯一确定的值与其对应,那么我们就把x称为自变量,把y称为因变...

1544
来自专栏tkokof 的技术,小趣及杂念

[译]C++17,optional, any, 和 variant 的更多细节

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/tkokof1/article/details/826...

1362
来自专栏逆向技术

逆向知识第七讲,三目运算符在汇编中的表现形式,以及编译器优化方式

                  逆向知识第七讲,三目运算符在汇编中的表现形式 一丶编译器优化方式 首先说一下编译器优化方式. 1.常量折叠 2.常量传播 3...

2768
来自专栏北京马哥教育

提升Python程序性能的7个习惯

使用局部变量替换模块名字空间中的变量,例如 ls = os.linesep。一方面可以提高程序性能,局部变量查找速度更快;另一方面可用简短标识符替代冗长的模块变...

860
来自专栏ShaoYL

iOS循环引用

3035
来自专栏進无尽的文章

编码篇-iOS程序中的内存分配 栈区堆区全局区等相关知识

在计算机的系统中,运行的应用程序中的数据都是保存在内存中,不同类型的数据,保存的内存区域不同。内存区域大致可以分为:栈区、堆区、全局区(静态区)、文字常量区、程...

2112

扫码关注云+社区

领取腾讯云代金券