面试题15:二进制中1的个数

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

思路:我想的蠢方法当然是一个个的检验二进制序列里面有没有1,但是这种方法也有陷阱。

方法1:判断整数二进制序列最右边是不是为1,判断方法可以是整数n与无符号数1进行位与,若结果为1,则最右边为1,否则,最右边为0;判断完一位后,将整数二进制向右移。这种方法有个很大的弊端:若n是个负数,一直右移右移,最后会变为0xFFFFFFFF,造成死循环。所以想到第二种常规方法。

方法2:既然移动整数会造成死循环,那就不要移动它。设置一个无符号标志位flag=1,左移flag与n进行位相与判断结果。例如,当flag=0x000...0001时,可以检查n最低位是否为1;flag左移变为0x000...0010可以检测n次低位是否为1....依次循环32次,到flag=0时检查完成。

代码:

int binary_system(int digit)
{
    unsigned long int flag = 1;
    int count = 0;
    while (flag)
    {
        if (digit & flag)
            count++;
        flag = flag << 1;
    }
    return count;
}

书上还有另一种完美方法,整数中有几个1就循环几次,不需要整32次。但我短时间肯定想不出这个鬼方法,不写了。

全部评论

相关推荐

10-28 11:04
已编辑
美团_后端实习生(实习员工)
一个2人:我说几个点吧,你的实习经历写的让人觉得毫无含金量,你没有挖掘你需求里的 亮点, 让人觉得你不仅打杂还摆烂。然后你的简历太长了🤣你这个实习经历看完,估计没几个人愿意接着看下去, sdk, 索引这种东西单拎出来说太顶真了兄弟,好好优化下简历吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务