首页 > 其他 > 详细

二进制数中1的个数

时间:2020-08-22 18:34:41      阅读:66      评论:0      收藏:0      [点我收藏+]

一、题目

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

二、解决方案

1. 避免死循环的位操作

时间复杂度为O(log2n)。

用位操作优于除法,考虑负数,比如n = 0x800000000,循环右移n可能会引起死循环。因此,可以循环左移1和n做与运算避免死循环。

/* 避免死循环的位操作 */
int NumberOf1_Solution1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while (flag)
    {
        if (n & flag)
            ++count;  //效率比count好
        flag <<= 1;
    }

    return count;
}

2. 位操作

时间复杂度为O(M),其中M为n中1的个数。

将n与(n-1)进行与运算,会把该数最右边的1变成0。那么1有多少个,就可以进行多少次与操作。

/* 最优的位操作 */
int NumberOf1_Solution2(int n)
{
    int count = 0;

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

    return count;
}

二进制数中1的个数

原文:https://www.cnblogs.com/yusq77/p/13546442.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!