二进制中1的个数

三月 25, 2019

Interview

题目描述

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

通过移位测试每一位

首先，很容易能想到的就是通过移位的方法，挨个判断每一位。

class Solution
{
public:
    int NumberOf1(int n)
    {
        int count = 0;

        while(n)
        {
            if(n & 1 == 1)
            {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
};

但是这种方法有个致命的缺陷，我们假设通过移位的方式可以获取到其每一位，但并不总是对的。

逻辑右移和算数右移

比如说一个有符号位的8位二进制数11001101，逻辑右移就不管符号位，如果移一位就变成01100110。算数右移要管符号位，右移一位变成10100110。

逻辑左移=算数左移，右边统一添0
逻辑右移，左边统一添0

算数右移，左边添加的数和符号有关

e.g:1010101010，其中[]位是添加的数字
逻辑左移一位：010101010[0]
算数左移一位：010101010[0]
逻辑右移一位：[0]101010101
算数右移一位：[1]101010101

因此如果输入负数，那么我们的算法简单的判断是不是0来终结，就会进入死循环。

避免负数移位的死循环

为了负数的时候，避免死循环，我们可以不右移数字n，转而去移动测试位。
那么思考我们的循环结束条件，flag一直左移（乘以2），当超出表示标识范围的时候，我们就可以终止了，但是这样子的话，最高位的符号没有测试，因此要单独测试，同时由于会溢出，我们的flag需要用long来标识。

class Solution
{
public:
    int NumberOf1(int n)
    {
        int count = 0;
        int i = 0;
        unsigned long flag = 1;

        while(flag <= INT_MAX)
        {
            cout <<n <<" & " <<flag <<" == "<<(n & flag) <<endl;
            if((n & flag) != 0)
            {
                count++;
            }
            flag <<= 1;
        }

        //  由于循环终结，我们使用的是flag <= INT_MAX
        //  因此前面的循环只会执行31次
        if((n & flag) != 0)    //  最后测试符号位
        {
            count++;
        }

        return count;
    }

};

继续考虑，会发现循环条件还可以精简一下，如果数据发生溢出的话，会被截断，截断以后就是0。

class Solution
{
public:
    int NumberOf1(int n)
    {
        int count = 0;
        int i = 0;
        unsigned int flag = 1;

        while(flag != 0)
        {
            cout <<n <<" & " <<flag <<" == "<<(n & flag) <<endl;
            if((n & flag) != 0)
            {
                count++;
            }
            flag <<= 1;
        }
        cout <<n <<" & " <<flag <<" == "<<(n & flag) <<endl;

        return count;
    }

};

这种方法循环的次数刚好就是二进制的位数，比如32位就循环32次。那么，有没有方法可以做到整数中有多少个1就循环多少次呢。

整数中有几个1就循环几次——lowbit优化

我们分析n与n-1两个数的差别

如果n!=0，那么其二进制位中至少有一个1
如果n的最低位是1（奇数），那么n-1正好把这个最低位的1变成0，其他位不变
如果n的最低位是0（偶数），那么假设其右起第一个1位于m位，即m位后面全是0，那么n-1的第m位由1变成0，而第m位后面的所有0均变成1，m位之前的所有位保持不变。
因此通过分析发现：
把一个整数n减去1，再和原来的整数做与运算，会把该整数最右边一个1变成0，那么该整数有多少个1，就会进行多少次与运算。

class Solution
{
public:
    int NumberOf1(int n)
    {
        int count = 0;
        while(n)
        {
            count++;
            n = n & (n - 1);
        }

        return count;
    }

};

STL-bitset

STL中用bitset来方便地管理一系列的bit位，而不用程序员自己来写代码。
bitset除了可以访问指定下标的bit位以外，还可以把它们作为一个整数来进行某些统计。

class Solution
{
public:
    int NumberOf1(int n)
    {
        bitset<32> bit(n);
        return bit.count();

    }

};

查看评论

1. 题目描述
2. 通过移位测试每一位
3. 逻辑右移和算数右移
4. 避免负数移位的死循环
5. 整数中有几个1就循环几次——lowbit优化
6. STL-bitset