题目主要信息

1、输入一个int整数，计算存储时1的个数

2、数据范围：32位整数范围内

3、输出1的个数

方法一：位运算

具体做法

第一眼看到这个题，可以想到之前做的剑指offer里面的一个经典的位运算的题目，求二进制中1的个数。

这里需要借助公式n&(n-1),该公式结果刚好是把n的二进制位中的最低位1变成0之后的结果。

例子：求5的二进制中1的个数

1. 5 & (5-1) = 4,5 = (101)2 , 4 = (100)2，从结果可以看出4就是把5的二进制位中的最低位1变成0之后的结果。
2. 4 & (4-1) = 0,4 = (100)2,0 = (000)2,此时n=0，可以结束。
3. 计数count = 2，所以5的二进制中有两个1.

因此在实际的计算中，我们可以让当前n与(n-1)做与运算，直到n为0为止，并用一个count计数遍历了多少次，就可以得到n的二进制有多少个1了。

Java代码

import java.io.*;
public class Main{
    public static void main(String []args) throws IOException{
        BufferedReader result = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(result.readLine());
        int count = 0;
        //直到num为0 截止
        while(num >0){
            count++;
            num  = num &(num -1);
        }
        System.out.println(count);
    }
}

复杂度分析

• 时间复杂度：$O(logn)O(logn)$。循环次数等于 $nn$ 的二进制位中 1 的个数，最坏情况下 $nn$ 的二进制位全部为 1。我们需要循环$lognlogn$次。
• 空间复杂度：$O(1)O(1)$，我们只需要常数的空间保存若干变量。

方法二：循环检查

具体做法

直接循环检查给定整数$nn$的二进制位的每一位是否为 1。

具体代码中，当检查第$ii$ 位时，我们可以让 $nn$ 与 $2^{i}2^i$进行与运算，当且仅当$nn$ 的第 $ii$位为 1 时，运算结果不为 0。

Java代码

import java.io.*;
public class Main{
    public static void main(String []args) throws IOException{
        BufferedReader result = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(result.readLine());
        int count = 0;
        for (int i = 0; i < 32; i++) {
            //判断当前位是否为1
            if ((num & (1 << i)) != 0) {
                count++;//如果为1就加1
            }
        }
        System.out.println(count);
    }
}

复杂度分析

• 时间复杂度：$O(1)O(1)$，其中$kk$ 是 型的二进制位数，$k=32k=32$。我们需要检查 n 的二进制位的每一位，一共需要检查 $3232$ 位。
• 空间复杂度：$O(1)O(1)$，我们只需要常数的空间保存若干变量。