描述

题目描述

输入一个正整数，计算它在二进制下的1的个数。

示例

输入：5
输出：2
说明：5的二进制表示是101，有2个1   

知识点：位运算

难度：⭐⭐

题解

方法一：移位统计

图解：

解题思路：

通过二进制的特性，每次进行最低为和1进行与运算，之后不断左移，并且最低位忽略，继续统计最低位是1还是0

算法流程：

• 对num进行最多32次运算的for循环
• 最低为的位运算，1 & 1 == 1, 0 & 1 == 0
• 不断左移，即最低位忽略，接下来继续统计最低位

Java 版本代码如下：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int num = scanner.nextInt();
        	System.out.println(solution(num));
        }
    }

    private static int solution(int num) {
        int res = 0;
        // 题目要求1<= num <= 2^32-1， 即二进制最多32位
        for(int i = 0; i < 32; i++) {
            // 位运算，1 & 1 == 1, 0 & 1 == 0
            if((num & 1) == 1) {
                res++;
            }
            // 左移，即最低位忽略，接下来继续统计最低位
            num = num >> 1;
        }
        return res;
    }
}

复杂度分析：

时间复杂度：$O(1)O(1)$，进行最多32次运算，属于常数级别的时间复杂度

空间复杂度：$O(1)O(1)$，没有开辟额外空间

方法二：二进制判断

解题思路：

转换位二进制后判断字符为1的个数

算法流程：

• 通过库函数将十进制数字转为字符串形式的二进制格式
• 判断字符为1的个数即可

Java 版本代码如下：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int num = scanner.nextInt();
        	System.out.println(solution(num));
        }
    }

    private static int solution(int num) {
        int res = 0;
        String bin = Integer.toBinaryString(num);
        for(char c : bin.toCharArray()) {
            if(c == '1') {
                res++;
            }
        }
        return res;
    }
}

复杂度分析：

时间复杂度：$O(n)O(n)$，n为输入数字的二进制位长度，需要遍历转换二进制后的每个字符

空间复杂度：$O(1)O(1)$，没有开辟额外空间