It has been 1197 days since the last update, the content of the article may be outdated.

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

我们通过将数字与 1 相与，即可知道数字的二进制的最后一位是否为 1，我们只要逐渐的将数字进行右移，即可统计出数字中 1 的数目，所以会写下这样的代码

public static int numbersOfOne(int n) {
    int count = 0;
    while (n != 0) {
        if ((n & 1) != 0) {
            count++;
        }
        n = n >> 1;
    }
    return count;
}

但是上面的代码有一个问题，那就是如果输入的整数为负数呢? 根据负数的表示原则，它的首位是 1 来表示数字的正负性，在右移的过程中，首位会进行补 1 以表示它的符号还是负的，这个时候统计出的数字就是错误的了，并且会造成上面代码的死循环，如下以 8 位表示的 −7 为例

为了解决负数引起的问题，我们可以反其道而行之，让 1 进行左移，然后与数字相与，同样也可以统计出数字 1 的个数，所以修改代码如下

public static int numbersOfOne(int n) {
    int count = 0;
    int flag = 1;
    while (flag != 0) {
        if ((n & flag) != 0) {
            count++;
        }
        flag = flag << 1;
    }
    return count;
}

但是我们发现统计负数中 1 的个数的结果与我们想象的不符，比如我们统计 −7 的个数，结果为

public static void main(String[] args) {
    System.out.println(numbersOfOne(-7)); // 30
}

结果是 30 而不是 4，难道是我们的算法错了，其实不是，而是计算机存储数字是以其补码进行存储的，对于正数来说，它的补码是它本身，而对于负数，则是将除符号位进行取反，然后加 1，所以 −7 的补码为

上面计算出一个数字二进制表示的 1 的个数需要进行 32 次循环(对于 int 类型的数据)，我们可以进一步对算法进行改进，使得二进制中有几个 1 则进行几次循环。为了理解下面讲的算法，我们来看一下将一个数字减去 1 它的二进制会发生什么变化?

先说结论，假设数字二进制最右边的 1 在第 m 位，即第 m 位后面的位全是 0，在减去 1 之后，第 m 位的 1 变成 0，后面的 0 全部变为 1，而第 m 位前面的数字保持不变，以 8 位表示的 10 为例

那么我们将数字 n 与 n−1 进行相与会得到什么，因为 n−1 第 m 位前面的数字不变，所以 n−1 的第 m 位以前的数字与 n 相同，所以 n & n−1 得到的第 m 位以前的二进制是不变的，而 n−1 第 m 位变成 0，以及第 m 位以后的 0 变为 1，所以 n & n−1 得到的第 m 位及第 m 位以后的二进制是 0，所以 n & n−1 的效果就是将数字 n 中最右边的 1 给去除了

所以我们就可以写出这样的代码

public static int numbersOfOne(int n) {
    int count = 0;
    while(n != 0) {
        count++;
        n = (n - 1) & n;
    }
    return count;
}

每次循环会去除一个 1，所以二进制中有几个 1，便会进行几次循环。

扩展：

  • 用一条语句判断一个整数是不是 2 的整数次方。一个整数如果是 2 的整数次方，那么它的二进制表示中有且只有一位是 1，而其他所有位都是 0。所以我们统计该数二进制中 1 的个数，如果是一个，那么就是 2 的整数次方。
  • 输入两个整数 m 和 n，计算需要改变 m 的二进制表示中的多少位才能得到 n。比如 10 的二进制表示为 1010，13 的二进制表示为 1101，需要改变 1010 中的 3 位才能得到 1101。我们可以分两步解决这个问题，首先将这两个数进行异或，这样 m 和 n 二进制不同的位会得到 1，相同的位是 0，我们只要统计异或后二进制中 1 的个数，即可得到需要改变的位数。