《图解数据结构算法》位运算总结笔记

发表于 更新于

总记

位运算，即“逐位运算”，指通过将数值转化为二进制的形式，再通过对二进制数位特性的分析解决实际问题的解题办法。本文通过分析LeetCode平台上《图解数据结构算法》一文中的位运算专题来介绍常见的位运算解题技巧。

方法总览

遍历

遍历一个十进制数的所有二进制数位是位运算中常见的操作，代码如下：

1
2
3
4
5
6
int result = 0;
for (int i = 0; i < 32; i++) {
    int digit = n & 1; // digit即为从右向左第i位数
    n >>= 1;
}
return result;

这种遍历方法在实际情况中多用于计算数的汉明重量。

模拟加法

实际上，我们可以通过模拟加法器的工作原理，来用位运算进行加减运算。

每个int类型的二进制信息由32个bit位储存，其中首位为符号位，其它31个数位则负责储存这个整数，我们容易知道，对于两个二进制数位相加，可能出现的情况如下表。

数位1 数位2 新的数位结果 进位
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

所以，基于加法原则，我们可以模拟加法器的行为写出加法器的逻辑代码。

1
2
3
4
5
6
7
8
9
public int EncryptionCalculate(int dataA, int dataB) {
    while (dataB != 0) {
        int carry = (dataB & dataA) << 1;
        dataA ^= dataB;
        dataB = carry;
    }
    return dataA;
}
// carry用于储存进位信息，每一轮异或运算后再计算进位

减法运算也同理，即为正数和负数之间相加，不过我们也应当同时搞懂负数在计算机中的储存方式。

反码：将某个数的所有二进制数位全部反转（即0变为1，1变为0）

补码：某个数的反码+1

可以论证，根据上述加法器运算原则，一个数的原码加上其补码一定等于0（从右到左最后一位数最终会在左移中溢出）

所以，为了方便运算，计算机储存负数的方法是储存一个数的补码，这样可以保证一个数和其相反数的和必定为0。

同时，我们可以知道，由于一个数的最高数位是符号位，所以作为正数（或0），其符号位一定为0；作为负数，根据补码原理推定，其符号位一定为1，这通常是我们判断一个数是否为负的依据。

综上所述，将一个数和另一个数的补码进行加法运算，即为减法的工作原理。

异或除重

异或运算是指对两个数进行逐位操作并返回一个具有如下性质的数：对于两个数的同一数位而言，如果它们的两个数位相同，则记该数该位为0；否则记该数该位为1。这种运算的真值表如下：

数位1 数位2 新的数位结果
0 0 0
0 1 1
1 0 1
1 1 0

容易知道，对于任意一个数x，规定异或运算符为^，则一定有x ^ x == 0成立，所以如果要找出在成对数据中单独出现的某个数，可以遍历数组并逐个异或，根据异或运算的交换律，最后剩下的数必定为那个单独的数。

异或除重运算的更普遍情况

在本书中，问题训练计划6的情况则更加复杂，一组数据流中只有一个数出现了一次，其他所有数都各自分别出现了三次，这样直接使用异或运算就没有用处了。

对此，我们可以推广异或运算。如果我们把视角固定在某一个具体的数位上，对数组中所有数进行分析，则该数位上的“1”总出现次数必定是3的整数倍或3的整数倍余1。这是因为除了一个数以外，所有的其他数都以三个一组出现。

所以，逐个统计某数位上1的出现次数，然后对3求余数，即可得出那个单独出现的数的情况，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int TrainingPlan(int[] actions) {
        // 统计各数位的1出现次数，对3取余，得到的数字即为答案
        int[] numSpeller = new int[32];
        for (int k = 0; k < actions.Length; k++) {
            for (int i = 0; i < 32; i++) {
                numSpeller[i] += actions[k] & 1;
                actions[k] >>= 1;
            }
        }
        int result = 0;
        int power = 1;
        for (int j = 0; j < 32; j++) {
            result += (numSpeller[j] % 3) * power;
            power *= 2;
        }
        return result;
    }
}

可以知道，异或运算是以2取余的上述方法的特殊情况。

后记

位运算的操作非常具有潜力，在特定情况下巧妙运用位运算可以提升运行效率，节省空间。