2024-05-18-位运算复习.md

发表于 | 分类于
刷题遇到了几次位运算的解题方式，复习一下

位运算分类和计算规则

位计算是底层运算，是对二进制或者整数对应的二进制直接计算的，算法设计和底层编程中用的比较多，熟悉位运算可以在算法解题中有种突袭胜利的快乐。

我不熟悉位运算了，失去了这种快乐，所以回来补习。

位与运算（AND、&&）

逐位进行与操作，只有当两个对应位都为 1 时结果才为 1，否则为 0。

A B A&B
0 0 0
0 1 0
1 0 0
1 1 1

位或运算（OR、 ||）

对两个二进制位进行或操作，只要其中一个位为 1，结果就为 1。

A B A or B
0 0 0
0 1 1
1 0 1
1 1 1

位非运算（NOT、～）

对一个二进制位进行取反操作，0 变 1，1 变 0。

A ~B
0 1
1 0

异或运算（XOR、^）

对两个二进制位进行，不同时结果为 1，当两个位相同时结果为 0。

A B A^B
0 0 0
0 1 1
1 0 1
1 1 0

异或运算的特性需要注意（关联LeetCode136 ）

  • 自反性：A ^ A = 0
  • 结合性：A ^ B = B ^ A
  • 结合律：A ^ (B ^ C) = (A ^ B) ^ C
  • 恒等律：A ^ 0 = A

亦或运算的典型应用：

  • 位反转：与1亦或运算，那么可以得到原值的按位取反
  • 不声明新变量的情况下交换两个变量的值： 
    1
    2
    3
    4
    5
    6
    int a = 5; // 0101
int b = 9; // 1001

a = a ^ b; // a = 0101 ^ 1001 = 1100
b = a ^ b; // b = 1100 ^ 1001 = 0101 (原来的 a)
a = a ^ b; // a = 1100 ^ 0101 = 1001 (原来的 b)

左移运算（«）

将一个数的二进制位左移指定的位数，右边补 0。

左移一位相当于乘以 2。

右移运算（»）

将一个数的二进制位右移指定的位数，左边根据符号位补 0（正数）或补 1（负数）。

右移一位相当于除以 2。

无符号右移运算（»>）

右移运算不区分正负一律补零的版本。 可能会吧一个很小的数字变成超大的正数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class UnsignedRightShiftExample {

  public static void main(String[] args) {
    int a = -5; // 二进制补码表示: 11111111111111111111111111111011

    // 右移 1 位，无符号右移
    int result = a >>> 1; // 结果: 01111111111111111111111111111101, 十进制为 2147483645

    // 打印原始值和结果
    System.out.println("原始值: " + a + " (" + Integer.toBinaryString(a) + ")");
    System.out.println(
        "无符号右移 1 位后的值: " + result + " (" + Integer.toBinaryString(result) + ")");
  }
}