题目描述

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

输入格式
第一行包含整数n。

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

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

数据范围
1≤n≤100000,
0≤数列中元素的值≤109
输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

算法1

思路

1.实现lowbit方法:返回二进制第一位1（从右往左）的值

2.一个数减去多少个lowbit后为0就有多少个1

Java 代码

import java.util.*;

public class Main {
    private static int N = 100010;
    private static int[] a = new int[N];
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 0;i < n;i++){
            a[i] = scanner.nextInt();
        }
        for(int i = 0,k = 0;i < n;i++){
            while(a[i] != 0){
                k++;
                a[i] -= lowbit(a[i]);
            }
            System.out.print(k + " ");
            k = 0;
        }
    }
    /*
    返回二进制第一位1（从右往左）的值
    如1010：返回0010
    */
    public static int lowbit(int x){
        return x & -x;
    }
}