位运算之美

发表于 更新于 分类于

简介

计算机底层用的是机器码，即0和1交织而成。位运算在某些情况下，有着神奇的功效，能够提升效率，节省空间。

  • 例如：

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1：

输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1] 示例 2：

输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]

可以采用异或操作得出两个不同数字的异或值(其他所有成对的数字异或后等于0)，最终的结果每一位上若为1则表示两数在此位上不同，反之为0则相同。随便取为1的一位(由于俩数不同，必存在为1的位)，将整个数组分为两组(以此位为0和一分别分两组)，这样两个不同的数必然会分到两个不同的组中。最后两个不同的组中组内依次异或，可以计算出不同的那一位，两组得到最终两个不同的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        x = 0
        for i in range(len(nums)):
            x ^= nums[i] # 求不同俩数异或结果
        t = x - (x&(x-1)) # 取最低位1，树状数组的典型操作，位运算优先级较低加括号
        ans = [0,0]
        for x in nums: # 分组并异或
            if t&x:
                ans[0] ^= x 
            else:
                ans[1] ^= x
        return ans

详解

  • 使用位运算求奇数偶数：
1
x&1==1	x&1==0

最低位为一为奇数，为零为偶数。用此方法的效率要高于一般的求余函数等操作。

  • 使用位运算来交换变量：
1
2
3
4
5
6
7
8
9
a ^= b;
b ^= a;
a ^= b;

第一步：a ^= b ---> a = (a^b);

第二步：b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a

第三步：a ^= b ---> a = (a^b)^a = (a^a)^b = b

比使用临时变量更高效率。

  • 交换符号将正数变成负数，负数变成正数：
1
~x+1

整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数.

  • 消去最低位1：
1
x&(x-1)

如果是x-(x&(x-1)则为最取最低位1，这是树状数组中典型的lowbit操作的根本依据。

  • 使用二进制进行子集枚举：
1
arr = [3,5,7]
编号 进制 子集
0 000 []
1 001 [3]
2 010 [5]
3 011 [3,5]
4 100 [7]
5 101 [3,7]
6 110 [5,7]
7 111 [3,5,7]

每一位代表当前数的取或者不取。

  • 找出现一次的数：

在一个数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数。此时将每个数依次异或一遍，出现次数为两次的(偶数次均可)，会相互抵消为0，剩下的就是只出现一次的数。

Bye

合理运用位运算可以有出其不意的效果，如开头提到的例子，如果用哈希表的话需要花费很多额外的空间，而使用位运算则只需常数复制度就可以解决这个问题。