提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
目录
前言
一、二进制中1的个数
二、算法思路
1.将一个整数转化成二进制形式
2.查询一个数的二进制数中的第k位是多少
3.lowbit(x)操作
三、代码如下
1.代码如下:
2.读入数据
3.代码运行结果
4.样例解释
总结
前言
主要通过位运算来完成两个基本操作,查询一个数的二进制数第k位数是什么,和lowbit操作返回一个二进制数中最右边的1所对应的数值,可以用来统计二进制中1的个数。
一、二进制中1的个数
给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数,表示整个数列。
输出格式
共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
数据范围
1≤n≤100000
0≤数列中元素的值≤1000000000
二、算法思路
1.将一个整数转化成二进制形式
图1.1示例图
将一个十进制数转换为二进制字符串,可以采用“除2取余数”的方法。具体步骤如下:
(1)将数字除以2。
(2)获取下一次迭代的整数商。
(3)获取其余的二进制数字。
(4)重复这些步骤,直到商等于0。
(5)将得到的所有余数全部排列起来,再将它反过来(逆序排列)。
上述图1.1中15的二进制数就是1111。
2.查询一个数的二进制数中的第k位是多少
图2.1示例图
我们需要查看哪一位二进制数,只需要这个数右移多少位然后再与1做与运算即可。查看第1位就是这个数右移0位再与1做与运算;第2位是右移1位再与1做与运算后续以此类推。
int x = 10;
for(int i = 3;i >= 0;i--){
pw.printf("%d",x >> i & 1);
}
运行结果: 1010
3.lowbit(x)操作
lowbit(x)函数的作用就是一个二进制数中最右边的1所对应的数值。
例如: x = 1010 lowbit(x) = ,返回值是int对应的十进制是2;
x = 10010000 lowbit(x) = ,返回值是对应的十进制是16。
图3.1与运算模拟
在计算机中我们常用补码来表示数据,其中第一位是符号位1表示正数,0表示负数。正数的原码、反码、补码全部相同;负数的反码是原码除了符号位全取反,补码是反码加1;从上述图3.1的过程中我们可以知道任意x和-x的补码对应的关系是-x的补码是x的补码连带符号位取反加1,最后二进制数中的最后一位1的后面x和-x相等,在二进制数中的最后一位1前面x和-x互相取反。
那么,进行与运算后二进制数中的最后一位1前面全部变成0,二进制数中的最后一位1后面的不变,此时就是二进制数中x的最后一位1和后面的二进制数。
注:(与运算 1 & 0 = 0 、0 &1 = 0、1 & 1 = 1 、 0 & 0 = 0)
//lowbit操作返回一个二进制数中最右边的1所对应的数值
public static int lowbit(int x){
return x & -x;
}
三、代码如下
1.代码如下:
import java.io.*;
public class 位运算 {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static void main(String[] args) throws Exception{
int n = nextInt();
while(n-- > 0){
int x = nextInt();
int res = 0;
while(x != 0){
//每一次减去x里面的最后一位1对应的数值,减了多少次就有多少个1
x -= lowbit(x);
res++;
}
pw.print(res+" ");
}
pw.flush();
}
public static int lowbit(int x){
return x & -x;
}
public static String next()throws Exception{
return br.readLine();
}
public static int nextInt()throws Exception{
st.nextToken();
return (int)st.nval;
}
}
2.读入数据
5
1 2 3 4 5
3.代码运行结果
1 1 2 1 2
4.样例解释
1对应的二进制为1,1的个数是1。
2对应的二进制为10,1的个数为1。
3对应的二进制为11,1的个数为2。
4对应的二进制为100,1的个数为1。
5对应的二进制为101,1的个数为2。
总结
主要通过位运算来完成两个基本操作,查询一个数的二进制数第k位数是什么,和lowbit操作返回一个二进制数中最右边的1所对应的数值,可以用来统计二进制中1的个数。