HelloBear

Less is More

0%

位运算

Posted on Edited on

本文介绍基本的位运算常见的使用方法。

基本位运算

常见的位运算包括位异或、位与、位非、位或和移位。其中异或包括交换律、结合律和自反性等。

python中的运算符如下：

位运算符 说明 使用形式 举 例
& 按位与 a & b 4 & 5
丨 按位或 a 丨 b 4 丨 5
^ 按位异或 a ^ b 4 ^ 5
~ 按位取反 ~a ~4
<< 按位左移 a << b 4 << 2，表示整数 4 按位左移 2 位
>> 按位右移 a >> b 4 >> 2，表示整数 4 按位右移 2 位

异或

首先介绍异或的三个性质：

  1. 任何数和0做异或运算，结果仍然是原来的数，即 aa⊕0=a；

  2. 任何数和其自身做异或运算，结果是0，即 a⊕a=0；

  3. 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

利用这些性质，我们可以做些什么呢？

1 面试题 16.01. 交换数字

这题要求我们不适用临时变量，为了交换两个变量a和b，这里用异或运算就可以实现：

1
2
3
a = a^b
b = a^b
a = a^b

2 136. 只出现一次的数字

这题给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

我们用异或的性质3，得到解为：

1
reduce(lambda x,y:x^y,nums)

3 268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

只要抓住了异或的性质，这种类型的题就都很容易做了：

1
2
3
def missingNumber(self, nums: List[int]) -> int:
    tmp = reduce(lambda x,y:x^y,range(len(nums)+1))
    return tmp ^ reduce(lambda x,y:x^y,nums)

移位

在我们实际使用中，用的主要都是十进制，那么为了实现二进制的操作，很多得依靠移位操作。

1 137. 只出现一次的数字 II

这题里面，看起来和上面的第二题很相似，但是本质确实不同的。这里一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现三次，请你找出并返回那个只出现了一次的元素。这题直接用异或操作就是不行的了。

考虑从每个元素都出现三次入手。如果从次数入手，我们可以想到能不能和什么东西整除3挂钩。因为除了某个元素，其他元素都是三个三个为一组的。

我们可以注意到：-2^31 <= nums[i] <= 2^31 - 1，这意味着我们处理的数据都是32位的数据。如果把每一个数字都看成二进制，那么一个十进制数nums[i]对应一个32位的二进制数。将所有nums[i]对应的二进制数的对应位求和，将每一对应位的和值与3进行取模运算，得到的余数就是答案的对应二进制位的数值。这是因为除了答案本身，其它元素都是三个三个为一组的。

上面的语言有些抽象，我们举个例子：

  • 如果输入是：nums = [2,2,3,2]，那么它的各个元素对应的32位二进制数就是[00000000000000000000000000000010, 00000000000000000000000000000010, 00000000000000000000000000000011, 00000000000000000000000000000010]；

  • 接着，对这些二进制数的对应位进行求和，得到：[00000000000000000000000000000041]；

  • 对这个求和结果的每一位进行3的取模运算，得到：[00000000000000000000000000000011]；

  • 把上面的结果从二进制转换为十进制，就是：3。这就是我们的答案。

在python中，为了实现上述的做法，就需要移位操作了：

1
2
3
4
5
6
7
8
9
10
11
def singleNumber(self, nums: List[int]) -> int:
    ans = 0
    for i in range(32):
        total = sum((num >> i) & 1 for num in nums)
        if total % 3:
            # Python 这里对于最高位需要特殊判断
            if i == 31:
                ans -= (1 << i)
            else:
                ans |= (1 << i)
    return ans

2 190. 颠倒二进制位

这题要求我们颠倒二进制位，我们也是先用移位取数，然后异或保存：

1
2
3
4
5
6
def reverseBits(self, n: int) -> int:
    ans = 0
    for i in range(32):
        tmp = (n >> i) & 1 
        ans |= (tmp << 32-i-1)
    return ans