位运算--(二进制中1的个数)
位运算是计算机科学中一种高效的操作方式,常用于处理二进制数据。在Java中,位运算通常通过位移操作符和位与操作符实现。
当然位运算还有一些其他的奇淫巧计,今天介绍两个常用的位运算方法:返回整数x的二进制第k位的值和返回x的最后一位1。
1. 返回x的二进制第k位的值
方法:x >> k & 1
示例
假设我们有一个整数x = 13(二进制为1101),而我们希望获取其第2位的值(从0开始计数),即 k = 2
:
int x = 13; // 二进制表示为 1101
int k = 2;
int bitValue = (x >> k) & 1; // (1101 >> 2) = 0011, 最后 & 1 = 1
System.out.println(bitValue); // 输出 1
原理解释
>>
代表右移运算符,它会将x的二进制位向右移动k位。&
代表位与运算符,它会将两个相应位进行比较,当两个相应位均为1时,结果为1,否则为0。
通过右移k位后,原本第k位的数据会移到最右侧,即最低位,接下来使用& 1
可以判断这个最低位的值是0还是1。
在这个例子中,右移2位后,二进制表示变为 0011
,然后通过& 1
获取最后一位的值,结果是1,说明x的第2位为1 。
2. lowbit(x) 返回x的最后一位1
方法:x & -x
示例
import java.io.BufferedInputStream;
import java.util.Scanner;/*** 位运算** 1.返回x的二进制第k位的值 x>>k & 1* 2.lowbit(x)返回x的最后一位1 x & -x*/public class Main {public static int lowbit(int x) {return x & -x;//返回x的最后一位1}public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt();//n为数列的长度while (n-- > 0) {int x = sc.nextInt();int res = 0;while (x > 0) {x -= lowbit(x);//每次减去x的最后一位1res++;}System.out.print(res+" ");//输出二进制中1的个数}}
}
原理解释
在这里,
-x
表示x的补码,补码的计算是通过对x进行按位取反后加1实现的。x & -x
的目的就是找到x的二进制表示中最右边的1所在的位置。通过这个运算,我们可以得到x的最后一位1,其他位均被清零
总结
位运算性能优越,适用于多种场景。通过介绍这两种基本位操作,我们可以更加深入地理解和运用位运算,从而提升编程效率。
希望能对你有所帮助……