剑指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)
blank

相关推荐

  • RAID 小结

    RAID 小结

  • 深度学习——SPPNet原理[通俗易懂]

    深度学习——SPPNet原理[通俗易懂]从R-CNN到FastR-CNN,有必要了解下SPPNet,其全称为SpatialPyramidPoolingConvolutionalNetworks(空间金字塔池化卷积网络)。它将CNN的输入从固定尺寸改进为任意尺寸,例如在CNN结构中,输入图像的尺寸往往固定的(如224×224像素),输出可看做固定维数的向量。SPPNet在普通的CNN结构中加入了ROI池化层(ROIPo…

  • NAT模式实现局域网物理机与虚拟机的互通访问「建议收藏」

    NAT模式实现局域网物理机与虚拟机的互通访问「建议收藏」玩过虚拟机的朋友都知道,不管是vbox还是vm,最常用的网络设置也不外乎3种:1、桥接模式:此模式下,虚拟机的操作系统就像和物理机同一段网络中的物理机一样,它可以访问网络中的任何机器,同时只要物理机可以访问网络,虚拟机也可以实现上网。此模式是懒人模式首选!但换来一个问题就是,如果你的物理机网络IP发生变化,虚拟机的IP也会相应的改变。如果IP变化对虚拟机有影响的环境,此模式慎用!

  • DDoS攻击的工具介绍[通俗易懂]

    DDoS攻击的工具介绍[通俗易懂]1.低轨道离子加农炮(LOIC)1.1什么是低轨道离子加农炮(LOIC)?低轨道离子加农炮是通常用于发起DoS和DDoS攻击的工具。它最初是由PraetoxTechnology作为网络压力测试

  • 大数据建模与分析挖掘相关了解「建议收藏」

    大数据建模与分析挖掘相关了解「建议收藏」一.大数据总体架构与规划二.各类数据的采集三.相关名词的了解MP:MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念”Map(映射)“和”Reduce(归约)”,是它们的主要思想,都是从函数式编程语言里借来的,还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。当前的软件实现是指定一个Ma…

  • 入门级都能看懂的softmax详解「建议收藏」

    入门级都能看懂的softmax详解「建议收藏」1.softmax初探在机器学习尤其是深度学习中,softmax是个非常常用而且比较重要的函数,尤其在多分类的场景中使用广泛。他把一些输入映射为0-1之间的实数,并且归一化保证和为1,因此多分类的概率之和也刚好为1。首先我们简单来看看softmax是什么意思。顾名思义,softmax由两个单词组成,其中一个是max。对于max我们都很熟悉,比如有两个变量a,b。如果a&gt;b,则max为…

发表回复

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

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