二进制中1的个数

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

我们通过将数字与 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
}

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

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

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

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

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

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

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

扩展：

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