二进制中1的个数

题目题目分析算法解析源代码

题目

给定一个长度为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.对于本题,有一种解法-lowbit.顾名思义,能够通过这种算法,找到输入数字的二进制的表示的 从低位算起第1个1,并返回.简言之,返回的是1后若干个零,如果输入的是10010000,那么返回的就是10000.

算法解析

lowbit算法:利用的是补码.如果输入的是x,那么-x其实在计算机内是以补码的形式存储的,也即是取反+1.而不论输入的是什么数,经过取反+1,只有低位是1000...这种形式的取反+1才不变,而其余任何的位都取反了,也就意味着之后低位是1000...这种形式的才值不变,其余位都已经变成了0. 因此 x&(-x) 得到的数就是原数的lowbit.(当然是int类型的) 更近一步的,如果想要得到各个数字的二进制的各个位数的值,其实要做的就是移位操作. 如果想到得到第i位(从低位开始数起,第0位就是最低位数),只需要将此数向右移位i位>>i,这样想要的位数其实就到了最低位,取这个数的操作就是对其做&1操作 也就是 x>>i&1 就会得到x的二进制第i位

源代码

import java.util.Scanner; class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); while(n-->0){ int x=sc.nextInt(); int temp; int count=0; while( (temp=x&(-x))!=0){ count++; x-=temp; } System.out.print(count+" "); } } }