面试题15. 二进制中1的个数

难度简单

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

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 **00000000000000000000000010000000** 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 **11111111111111111111111111111101** 中，共有 31 位为 '1'。

int 占 4 个字节，一个字节占 8 位，int 占 36 位。 在计算机内存中以二进制来表示数字，例如int n = 9，n 在内存中表示为 00000000000000000000000000001001 ，
解答：
第一种思路
逐位计算，将 n 与 1 进行与运算，如果结果为 1， 则 result ++。每次与运算后，将 n 向右移1位。循环移动，直到 n == 0；
例如 int n = 9， 二进制位表示为 1001。
1001 & 0001 = 1， 1001 >>> 1 = 100。

public class Solution {
   // you need to treat n as an unsigned value
   public int hammingWeight(int n) {
       int result = 0;
      
       while( n != 0){
         if((n & 1) == 1)
           result ++;
         n >>>= 1;  // >>> : Java 中表示无符号的移位，使用 >> 会超时。 
       }
       
       return result;
   } 
}

时间复杂度为 O(n)，n 是 二进制的长度。
空间复杂度为 O(1)。

第二种
利用 n & (n-1)。
n-1: 将n中最右边的1 变为 0，最右边 1 的右边所有 0 变 1，例如 11000 (24)， 减一后， 10111 (23)。
n & ( n-1 ) : 将n中最右边的 1 变为 0， 例如 11000 & 10111 = 10000。
循环利用 n & (n-1)，每次能将 n 中最右边的 1 去掉。直到 n == 0 退出循环， n 中有多少个1，循环就进行多少轮。所以可以统计循环的次数，即能得到 n 中有多少个1。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        while( n != 0){
            result ++;
            n = n & (n-1);
        }
        return result;
    } 
}

时间复杂度：O(m) : m 为二进制数中 1 的个数。
空间复杂度为 O(1)

利用第二种方法，大大提升了运行的时间。