题意整理。

  • 输入一个int型的正整数。
  • 输出这个数转化位二进制之后1的个数。

方法一（按位统计）

1.解题思路

  • 定义一个变量，用于记录二进制中1的个数。
  • 遍历输入整数的每一位，如果当前位是1，则计数加1。直到统计完所有的位。

图解展示： alt

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //记录二进制中1的个数
        int count=0;
        while(n!=0){
            //如果当前位是1，计数加1
            if((n&1)==1){
                count++;
            }
            //右移一位
            n>>=1;
        }
        System.out.println(count);
    }
}

3.复杂度分析

  • 时间复杂度：假设输入整数为n，需要遍历n的每一位，所以时间复杂度为O(log2n)O(log_2n)。
  • 空间复杂度：不需要额外的空间，所以空间复杂度为O(1)O(1)。

方法二（位运算）

1.解题思路

  • 定义一个变量，用于记录二进制中1的个数。
  • 遍历输入整数的每一个为1的位，计数加1。直到输入的数变为0。

与方法一不同的是，此方法只需遍历为1的位，如果1的数目比较少，则复杂度会大大地减小。

n&(n-1)之后就会去掉最右边的1，对于这个问题的解释，可以将n以最右1为边界分为两部分，n和n-1的左部分肯定是相同的，所以相与之后不会发生变化，而n的右部分一定是类似1000……0这样的结构，而n-1的右部分一定是类似0111……1这样的结构，相与之后就变成了全0。所以最后的结果刚好是去掉了最右1。

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //记录二进制中1的个数
        int count=0;
        while(n!=0){
            //操作之后，相当于去掉最右边的1
            n=n&(n-1);
            //计数加1
            count++;
        }
        System.out.println(count);
    }
}

3.复杂度分析

  • 时间复杂度：最坏情况下，所有位都是1，所以时间复杂度为O(log2n)O(log_2n)。
  • 空间复杂度：不需要额外的空间，所以空间复杂度为O(1)O(1)。

方法三（最右1）

1.解题思路

与方法二的思路基本相同，不过是先求出最右边的1，然后再在原数的基础上减去最右1。求最右1的方法可被用于设计树状数组。

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //记录二进制中1的个数
        int count=0;
        while(n!=0){
            //记录当前最右边的1
            int rightone=n&(-n);
            //减掉最右1
            n-=rightone;
            //计数加1
            count++;
        }
        System.out.println(count);
    }
}

3.复杂度分析

  • 时间复杂度：最坏情况下，所有位都是1，所以时间复杂度为O(log2n)O(log_2n)。
  • 空间复杂度：不需要额外的空间，所以空间复杂度为O(1)O(1)。