力扣150题——位运算
位运算概述
位运算（Bitwise Operation）是计算机底层操作中的一种，用来直接对整数的二进制位进行操作。位运算通常速度很快，且消耗的内存较少，在处理一些特定问题（如加密算法、图像处理、低级硬件编程等）时非常有用。
常见的位运算符
位运算符用于直接操作整数的二进制位。以下是 Java 中常见的位运算符：
-
按位与（&）
逐位比较两个数的二进制表示，只有对应位都为 1，结果的该位才为 1，否则为 0。
示例：5 & 3
5的二进制为01013的二进制为00110101 & 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;
}