【剑指Offer】二进制中1的个数
发布日期:2022-02-10 08:55:11 浏览次数:34 分类:技术文章

本文共 1300 字,大约阅读时间需要 4 分钟。

题目描述

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

思路

正数正常思路走,最低位和1相与,然后右移一位,直到为0,就可判断出结果。但负数不行,负数最高位是1,右移以后最高位补1,所以就会死循环,因此判断正负数,负数的话就直接取反,然后判断,最后结果拿32(int四字节32位)减掉计数即为正确答案。

牛客上有更好的办法:

 

最佳答案及分析:

public class Solution {

    public int NumberOf1(int n) {

        int count = 0;

        while(n!= 0){

            count++;

            n = n & (n - 1);

         }

        return count;

    }

}

分析一下代码: 这段小小的代码,很是巧妙。

如果一个整数不为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,就可以进行多少次这样的操作。

代码

class Solution {public:     int  NumberOf1(int n) {         if(n == 0){             return 0;         }         if(n > 0){             int count = 0;             while(n != 0){                 if( (n & 1) == 1){                     count++;                 }                 n = n >> 1;             }             return count;         }         if(n < 0){             int count = 0;             int n1 = ~n;             while(n1 != 0){                 if( (n1 & 1) == 1){                     count++;                 }                 n1 = n1 >> 1;             }             return 32 - count;         }     }};

 

转载地址:https://blog.csdn.net/hanmin822/article/details/105464302 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【剑指Offer】二叉树的镜像
下一篇:【剑指Offer】数值的整数次方

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月22日 13时21分02秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux crontab 备份数据库 空文件,Linux下使用crontab自动备份数据库 2019-04-21
linux批处理模式,巧用linux-top的批处理模式 2019-04-21
linux信号量机制例题,第二章 信号量机制及几个经典例题 2019-04-21
linux ba 模拟,在你的 Python 游戏中模拟引力 | Linux 中国 2019-04-21
c语言表达式3649的值是,535个C语言经典实例目录.doc 2019-04-21
c语言Wndproc未定义,小弟我用c语言写了一个windows窗口,为什么有提示未定义的变量类型... 2019-04-21
c语言中malloc数组,如何在C中对malloc()数组进行一行赋值? 2019-04-21
c语言调存储过程,写留言板–调用存储过程出问题 2019-04-21
c语言编程max,C语言编程题及答案.doc 2019-04-21
android测试页面,自动执行界面测试 | Android 开发者 | Android Developers 2019-04-21
android 图片点击变色,Android开发实现ListView点击item改变颜色功能示例 2019-04-21
android增删改查布局,Android之父_增删改查 2019-04-21
vowifi android开关,如何配置VoLTE, ViLTE and VoWifi(IMS config for VoLTE, ViLTE and VoWifi) 2019-04-21
电脑端的mafsvr服务关掉_网吧才是电脑优化的精髓!学会3招你也不用羡慕网吧的流畅了... 2019-04-21
html获取文件路径_HTML 文件路径 2019-04-21
mysql滴的一声就关了_关于mysql数据库在输入密码后,滴的一声直接退出界面的解决办法(详细办法)... 2019-04-21
mysql in 有序_mysql中的in排序 mysql按in中顺序来排序 2019-04-21
mysql 行转列 显示_mysql 行转列 (结果集以坐标显示) 2019-04-21
mysql 完全备份恢复吗_MySQL完全备份与恢复 2019-04-21
wpf 绘制矩形_WPF制作倒影效果 2019-04-21