面试题【8】二进制中 1 的个数

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

分析：通常为了解决这个问题，我们会将每一位与 1 进行 & 运算，然后将这个数 右移（>>） 一次。那么根据这种思想，我们写出下面这样的代码：

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

这种解法看上去没有问题，但我们考虑一下，如果输入的是一个负数，例如：0x8000 0000 ，将它右移一位时，并不是我们所想的简单的变成 0x4000 0000 ，而是 0xC000 0000。对于一个负数，右移一次，高位会补 1 ，这是因为移位前是一个负数，移位后要保持仍然是个负数。那么就会出现一个问题，当出现 0xFFFF FFFF时，上述代码就会是一个死循环。

为了克服这个问题，我们不再对 需要判断的数 进行移位，而是左移 1 。 什么意思？

例如：对于数 0x1101（二进制：0001 0001 0000 0001）； 第一次 与 1 进行 & 运算时，count + 1，随后将 1 左移一次，变成 2 （10），其实就是判断次低位是否为 1。判断的次数取决于数据类型的大小，通常为了判断一个 int 类型的数字，我们会使用 unsigned int 进行判断，那么也就是要循环 32 次，代码如下：

int NumberOf1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)
            count++;
        flag = flag << 1;
    }
    return count;
}

那么这样的解法的确解决了死循环的问题，但是并不是最完美的。

下面介绍一种更加高效的解法：

讲述这种解法之前，先对 一个数 减 1 的情况进行分析。 例如：对一个二进制数 1010**10**，当 对它减 1 时，变为 1010**01**，将这两个数相与 得到 1010**00**；再减 1 时，变为 10**0111**，再与 10**1000** 相与 得到10**0000**。我们可以发现，当对一个数减 1 时，做右边的 1 会变为 0 ，并且最右边 1 的右边 所有的 0 会变为1 ，这样两者相 与 会使得 最右边的 1 变为 0 。 通过这种思想，我们可以实现一种更加简便高效的方法：

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        ++count;
        n = (n - 1) & n;
    }
    return count;
}

相关题目： 1.用一条语句判断一个整数是不是 2 的整数次方。例如：8， 16， 32，这些数都有一个共同特点就是写成二进制时，只有 1 位 为 1 ，其他都是 0 。

bool JudgePowerOf2(int n)
{
    int count = 0;
    while(n)
    {
        ++count;
        n = (n - 1) & n;

        if(count >= 2)
            return false;
    }
}

2.输入两个数 m 和 n ，计算需要改变 m 的二进制表示中多少位 才能得到 n 。比如说，10 的二进制 1010，13的二进制 1101 ，需要改变 1010 的 3 位才能得到 1101 。 如何解决这个问题呢？ 其实，我们只要能求出两个数有多少位是不同的就可以了，那么通过 异或 ，我们可以将两个数中不同的位都变成 1 ，这样再使用上面的方法就可以了。

#include <iostream>

using namespace std;

void CountBinoryOf2(int num1, int num2)
{
    int num = num1 ^ num2;
    int count = 0;
    while (num)
    {
        ++count;
        num = (num - 1) & num;
    }
    cout << "需要改变" << count << "次" << endl;
}

int main()
{
    int number1, number2;
    cout << "请输入两个整数" << endl;
    cin >> number1 >> number2;

    CountBinoryOf2(number1, number2);

    return 0;
}

测试：100 与 17，需要 5 次。