侧边栏壁纸
博主头像
CoderKui

坐中静,舍中得,事上练

  • 累计撰写 51 篇文章
  • 累计创建 69 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

位运算

CoderKui
2021-12-07 / 0 评论 / 0 点赞 / 281 阅读 / 304 字 / 正在检测是否收录...

位运算

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 + " ");
        }
    }
}
0

评论区