位运算概述
位运算(Bitwise Operation)是计算机底层操作中的一种,用来直接对整数的二进制位进行操作。位运算通常速度很快,且消耗的内存较少,在处理一些特定问题(如加密算法、图像处理、低级硬件编程等)时非常有用。
常见的位运算符
位运算符用于直接操作整数的二进制位。以下是 Java 中常见的位运算符:
-
按位与(&)
逐位比较两个数的二进制表示,只有对应位都为 1,结果的该位才为 1,否则为 0。
示例:5 & 3
5
的二进制为0101
3
的二进制为0011
0101 & 0011 = 0001
结果为1
。
-
按位或(|)
逐位比较两个数的二进制表示,只要对应位有一个为 1,结果的该位为 1。
示例:5 | 3
0101 | 0011 = 0111
结果为7
。
-
按位异或(^)
逐位比较两个数的二进制表示,只有对应位不相同,结果的该位为 1,否则为 0。
示例:5 ^ 3
0101 ^ 0011 = 0110
结果为6
。
-
按位取反(~)
对一个数的每一位取反,即 0 变为 1,1 变为 0。
示例:~5
5
的二进制为0101
取反后为1010
,即-6
(在计算机中负数用补码表示)。
-
左移(<<)
将二进制位整体左移,右侧补 0,相当于乘以 2 的若干次方。
示例:5 << 1
5
的二进制为0101
左移 1 位后为1010
,即10
。
-
右移(>>)
将二进制位整体右移,左侧用符号位(正数补 0,负数补 1)填充,相当于除以 2 的若干次方。
示例:5 >> 1
5
的二进制为0101
右移 1 位后为0010
,即2
。
-
无符号右移(>>>)
不管正负,左侧都用 0 填充,右移。
示例:-5 >>> 1
-5
的二进制为11111111111111111111111111111011
右移 1 位后为01111111111111111111111111111101
,即2147483645
。
位运算的常见应用
- 奇偶判断
判断一个数是否为偶数:n & 1 == 0
,如果最低位是 0,则该数是偶数。
- 交换两个数
不使用额外变量交换两个数:
a = a ^ b;
b = a ^ b;
a = a ^ b;
- 清除最低位的 1
清除最低位的 1:n = n & (n - 1)
,常用于统计一个数的二进制表示中有多少个 1。
- 获取最低位的 1
获取最低位的 1:n & -n
。
- 乘法和除法优化
乘以 2 的 n 次方:a << n
除以 2 的 n 次方:a >> n
位运算的优势
- 速度快:因为位运算是在底层直接操作二进制数据,运算速度非常快。
- 节省空间:位运算可以使用更少的内存来表示复杂的信息。
- 应用广泛:适用于底层硬件编程、加密、图像处理等领域。
通过位运算,许多看似复杂的问题可以简化为高效的操作,因此在编写高性能程序时经常使用。
题解
颠倒二进制位
题目
190. 颠倒二进制位 - 力扣(LeetCode)
思路
- 遍历 32 位整数的每一位。
- 通过位移操作,将该位移动到正确的位置。
- 利用按位或 (
|
) 和移位操作,构造颠倒后的数字。
代码
public int reverseBits(int n) {int result = 0;for (int i = 0; i < 32; i++) {int lastBit = n & 1;result = (result << 1) | lastBit;n >>= 1;System.out.println(lastBit+" "+result+" "+n);}return result;}
位1的个数
题目
191. 位1的个数 - 力扣(LeetCode)
思路
- 遍历 32 位整数的每一位。
- 通过异或,判断是否为1
- 计数并移位
代码
public int hammingWeight(int n) {int sum=0;for(int i=0;i<32;i++){if((n&1)==1){sum++;}n>>=1;}return sum;}
只出现一次的数字Ⅱ
题目
137. 只出现一次的数字 II - 力扣(LeetCode)
思路
我们使用两个变量 ones 和 twos 来分别表示二进制位的不同状态:
- ones 表示当前位出现了 1 次;
- twos 表示当前位出现了 2 次。
对于每个数字 num,我们按位更新 ones 和 twos:
- 当一个数的某一位已经在 ones 中,我们将它加到 twos 中;
- 如果某一位已经在 twos 中,我们就将它清除。
代码
public int singleNumber(int[] nums) {int one=0;int two=0;for(int num:nums){two=two|(one&num);one=one^num;int t=~(one&two);one=one&t;two=two&t;}return one;}
数字范围按位与
题目
201. 数字范围按位与 - 力扣(LeetCode)
思路
- 如果 left 和 right 的某些高位不同,则在这个不同位及更低的位上,所有数的按位与结果一定为 0
- 因此问题可以转化为寻找left和right的公共前缀,再将其左移n位,n为寻找公共前缀移位的长度
代码
public int rangeBitwiseAnd(int left, int right) {int sum = 0;while(left!=right){left=left>>1;right=right>>1;sum++;}return left<<sum;}