位运算

位运算

n & 1 = n

看n的第k位数字是0还是1 ： n >> k & 1

-n == ~n + 1

例子：

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

输入格式

第一行包含整数 nn。

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

输出格式

共一行，包含 nn 个整数，其中的第 ii 个数表示数列中的第 ii 个数的二进制表示中 11 的个数。

数据范围

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

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        while(q-- > 0) {
            int res = 0;
            int n = sc.nextInt();
            while(n != 0) {
                n -= n & ~n + 1; // ~n + 1 即为数的补码，即该数的负数， n & n的负数为最后一位1的位置
                res++;           //所以每次n减去最后一位1开始的数，就为1的数量，直到n为0
            }
            System.out.print(res + " ");
        }
    }
}