算法训练 -- 第一章 线性表

一、位操作

所有数据在计算机底层都是以二进制形式存在的
存储时：数据以二进制数字形式进行存储
计算时：数据以补码形式参与运算，计算结束后再将结果转换回原码

1. 原码与补码

原码：首位符号位 + 数值位
  5：0000 0000   0000 0000   0000 0000   0000 0101
 -5：1000 0000   0000 0000   0000 0000   0000 0101

反码：中间状态 -- 原码数值位按位取反，符号位不变
  5：0000 0000   0000 0000   0000 0000   0000 0101
 -5：1111 1111   1111 1111   1111 1111   1111 1010

补码：反码 + 1，符号位参与运算
  5：0000 0000   0000 0000   0000 0000   0000 0101
 -5：1111 1111   1111 1111   1111 1111   1111 1011

规律：
  正数的 补码 == 原码，反之亦然
  负数的 补码 = 原码数值位按位取反 + 1
  负数的 原码 = 补码数值位 - 1 再按位取反

2. 位运算

&（按位与，and）：两数补码逐位比较，同1为1，有0为0，符号位参与计算
| （按位或，or）：两数补码逐位比较，有1为1，同0为0，符号位参与计算
^（按位异或，xor）：两数补码逐位比较，不同为1，相同为0，符号位参与计算
~（按位取反，not）：1变为0，0变为1（自运算）
<<（左移n位，shl）：a << b -- 二进制数a的补码左移b位，右侧补0，符号位不变
>>（右移n位，shr）：a >> b -- 二进制数a的补码右移b位，左侧补原符号位的值（即，正数补0，负数补1）
>>>（无符号右移n位）：a >>> b -- 将二进制数a视为正数，再将其补码（即其自身）右移b位，左侧补0

特别注意：所有数据（底层存储为二进制数字）都是以其 二进制补码 形式参与位运算的！

例如，计算机中 -5 除以 4 应该等于多少呢？

代码测试：

public static void main(String[] args) {
    int a = -5;
    System.out.println(a + " 除以 4 等于 " + (a / 4) + " 余 " + (a % 4));
}

执行结果：

-5 除以 4 等于 -1 余 -1

而 -5 右移 2 位等于多少呢？结果还是 -1 吗？

代码测试：

public static void main(String[] args) {
    int a = -5;
    System.out.println(a + " 右移 2 位为 " + (a >> 2));
}

执行结果：

-5 右移 2 位为 -2

？？？（十分疑惑）
教科书上不是经常写：右移 1 位 == 除以 2；右移 2 位 == 除以 4 吗？
那为什么一个负数右移 2 位的结果和其除以 4 的结果不同呢？

这是因为 -5 在参与右移运算前，要先转换成二进制补码形式
原码：1000 0000   0000 0000   0000 0000   0000 0101
补码：1111 1111   1111 1111   1111 1111   1111 1011
补码右移 2 位，由于是负数，左侧补1
结果：1111 1111   1111 1111   1111 1111   1111 1110
由于结果是负数，因此其原码 = 补码 - 1 再按位取反，符号位不变
结果原码：1000 0000   0000 0000   0000 0000   0000 0010
结果对应的数字值为：-2

3. 位运算的应用

1）与运算 实现 取模运算
  33 % 16 = 1
  33 &（16 -1）= 1
2）与运算 实现 奇偶性判断
  5 & 1 = 1
  4 & 1 = 0
3）与运算 实现 取整数的二进制码中最低位的“1”所代表的数值
   -- 树状数组（BIT，二叉索引树）核心算法
  4 & -4 = 4   0000 0100 & 1111 1100 = 0000 0100
  5 & -5 = 1   0000 0101 & 1111 1011 = 0000 0001
  6 & -6 = 2   0000 0110 & 1111 1010 = 0000 0010
  7 & -7 = 1   0000 0111 & 1111 1001 = 0000 0001
  8 & -8 = 8   0000 1000 & 1111 1000 = 0000 1000
4）异或运算的 还原特性
  异或运算有类似于“负负得正”的特性：
  一个数与另一个数做两次异或运算后，结果与运算前相同，即：a ^ b ^ b == a
  这种性质可以在不使用中间变量的情况下交换两个整型变量的值

public static void main(String[] args) {
    int a = -5;
    int b = 4;
    a = a ^ b;
    b = a ^ b; // b = a ^ b ^ b = a
    a = a ^ b; // a = (a ^ b) ^ (a ^ b ^ b) = b
    System.out.println("a = " + a);
    System.out.println("b = " + b);
}

执行结果：

a = 4
b = -5