题目15：二进制中1 的个数

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。

举例说明

例如，把9表示成二进制是1001，有2位是1。因此如果输入9，则该函数输出2。

思路

一. 利用Integer类的bitCount()

代码实现

public class _15 {
	public static int numberOfOne(int n) {
	    return Integer.bitCount(n);
	}

    public static void main(String[] args) {
    	System.out.println("数字 9的二进制表示中的1的个数:"+numberOfOne(9));//2
    }
}

输出：

1	数字 9的二进制表示中的1的个数:2

二. 常规循环

时间复杂度$O(logN)$

因为是统计1的个数，那么用输入整数的每一位与1的位与运算就可以简单的实现

代码实现

public class _15 {
    public static int numberOfOne(int n) {  
        int result = 0;// 记录数字中1的位数
        for (int i = 0; i < 32; i++) {//int占32bit
            result += (n & 1);
            n >>>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
    	System.out.println("数字 9的二进制表示中的1的个数:"+numberOfOne(9));//2
    }
}

输出：

1	数字 9的二进制表示中的1的个数:2

三. n&(n-1)

时间复杂度$O(logM)$，其中 M 表示 1 的个数。

一个结论

结论：一个数与该数减一的结果进行与运算n&(n-1)，会把该数右边（低位）第一个1变为0，而该位左边保持不变（高位）

例子：比如1100（对应十进制是12），减去1之后的结果是1011（也就是十进制的11），两个数进行与运算之后，我们发现最后的结果是1000（对应十进制的8，当然这个8与后面没有关系，可以略过）。这样我们每进行一次的与运算就消去一个1，这样消到最后肯定是0了，所以我们可以在代码中以这个为循环的终止条件。

代码实现

public class _15 {
    public static int numberOfOne(int n) {
        int result = 0;// 记录数字中1的位数
        while (n != 0) {// 数字的二进制表示中有多少个1就进行多少次操作
            result++;
            // 从最右边的1开始，每一次操作都使n的最右的一个1变成了0，
            // 即使是符号位也会进行操作
            n = (n - 1) & n;
        }
        return result;
    }

    public static void main(String[] args) {
    	System.out.println("数字 9的二进制表示中的1的个数:"+numberOfOne(9));//2
    }
}

输出：

1	数字 9的二进制表示中的1的个数:2

15:二进制中1 的个数

题目15：二进制中1 的个数

举例说明

思路

一. 利用Integer类的bitCount()

代码实现

二. 常规循环

代码实现

三. n&(n-1)

一个结论

代码实现

相关题目：

2的幂

从m变成n,改变的bit数目