剑指Offer面试题:8.二进制中1的个数建议收藏

一题目:二进制中1的个数二可能引起死循环的解法00001010>>2=0000001010001010>>3=11110001那么,问题来了:上面的方法如果输入一个

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

剑指Offer面试题:8.二进制中1的个数建议收藏此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

一 题目:二进制中1的个数

题目:请实现一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9,该函数输出2。

二 可能引起死循环的解法

// 计算整数的二进制表示中1的个数
int CalcOneNumInBinary(int nVal)
{
    int nCount = 0;
    while (nVal > 0)
    {
        if (1 == (nVal & 1))
        {
            nCount ++;
        }

        nVal = nVal >> 1;
    }
    return nCount;
}

PS:右移运算符m>>n表示把m右移n位。右移n位的时候,最右边的n位将被丢弃。
如果数字原先是一个正数,则右移之后在最左边补n个0;如果数字原先是负数,则右移之后在最左边补n个1。例如下面对两个八位二进制数进行右移操作:

00001010>>2=00000010

10001010>>3=11110001

那么,问题来了:上面的方法如果输入一个负数,比如0x80000000,如果一直做右移运算,最终这个数字就会变成0xFFFFFFFF而陷入死循环

三 避免死循环的解法

  为了避免死循环,我们可以不右移输入的数字i:

  (1)首先把i和1做与运算,判断i的最低位是不是为1。

  (2)接着把1左移一位得到2,再和i做与运算,就能判断i的次低位是不是1。

  (3)这样反复左移,每次都能判断i的其中一位是不是1。

int CalcOneNumInBinary_1(int nVal)
{
    int nCount = 0;
    int nFlag = 1;
    while (nFlag > 0)
    {
        if ((nVal & nFlag) > 0)
        {
            nCount ++;
        }

        nFlag = nFlag << 1;
    }
    return nCount;
}

四 高效新颖解法

int NumberOf1Solution3(int n)
    {
        int count = 0;

        while (n > 0)
        {
            count++;
            n = (n - 1) & n;
        }

        return count;
    }
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120167.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • gmapping matlab实现_gmapping学习

    gmapping matlab实现_gmapping学习一、机器人地图机器人地图一般分为三种类型:栅格地图,拓扑地图,特征地图1、栅格地图栅格地图栅格地图,在物流信息技术中有所涉猎,其就是构建一个个“小方块”,利用颜色信息来区分的地图的位置信息。在机器人建图中,栅格地图容易构建,表示且保存位置的唯一,对于短路径的规划方便;但栅格地图的路径规划效率不高,空间浪费(栅格的分辨率不依赖于环境的复杂度)并且也需要精确的机器人位置估计,其对于物体识别的人机交互问…

  • 什么是A记录  域名

    什么是A记录  域名

  • termux更改镜像源_pycharm自带python

    termux更改镜像源_pycharm自带python方法1在使用pip命令进行安装的时候,传入镜像地址如下#pipinstallpandas-ihttps://mirrors.aliyun.com/pypi/simple#pipinstalldjango==1.11.*-ihttps://pypi.tuna.tsinghua.edu.cn/simple可选的镜像地址有豆瓣https://pypi.douban.com/simple阿里云https://mirror…

  • oracle数据库904_oracle00933怎么解决

    oracle数据库904_oracle00933怎么解决今天早上在日志中发现exp备份时出错:..exportingtableBJ_AFFILIATES37rowsexportedEXP-00008:ORACLEerror904encounteredORA-00904::invalididentifier..exportingtable…

  • Java finalize方法使用

    Java finalize方法使用《JAVA编程思想》:java提供finalize()方法,垃圾回收器准备释放内存的时候,会先调用finalize()。         (1).对象不一定会被回收。      (2).垃圾回收不是析构函数。      (3).垃圾回收只与内存有关。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号