题目：请实现一个函数，输入一个整数，输出该数二进制表示中 $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$ 的个数，即可得到需要改变的位数。