描述

题目描述

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

示例

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

知识点:位运算

难度:⭐⭐


题解

方法一:移位统计

图解

image-20211209125539386

解题思路:

通过二进制的特性,每次进行最低为和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),没有开辟额外空间