题目描述

给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。

输入格式

第一行包含整数n。
第二行包含n个整数，表示整个数列。

输出格式

共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。

数据范围

1≤n≤100000,
0≤数列中元素的值≤109

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

具体代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();

        while (n-->0){
            int x=scanner.nextInt();
            int res=0;
            while (x!=0){
                x-=lowbit(x);
                res++;
            }
            System.out.print(res+" ");
        }
    }

    private static int lowbit(int x) {
        return x & (-x);
    }
}

算法分析

lowbit(x)：是求二进制最低为1 的值，意思是将x转化为二进制，只保留最低的1及其后面的0,具体的方法为 x & (-x) 其中 -x代表x的补码

比如，x=6
6的二进制为0000 0110
-6的二进制就是1111 1010
6 & (-6) =》 0000 0010 ，结果为：2

另：
在二进制中有四种码：
原码：用于表示真值
反码：用于求反
补码：用于数据的表示与存储
移码：用于浮点数阶码表示