位运算 - 简书

a = 60  # 0011 1100
b = 13  # 0000 1101

运算符	描述	示例
&	按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0	a& b: 0000 1100
\|	按位或运算符：只要对应的二个二进位有一个为1时，结果位就为1。	a\|b: 0011 1101
~	按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1 。~x 类似于 -x-1	~a: 1100 0011
^	按位异或运算符：当两对应的二进位相异时，结果为1	a^b: 0011 0001
<<	左移动运算符：运算数的各二进位全部左移若干位，由 << 右边的数字指定了移动的位数，高位丢弃，低位补0。	a<<2: 1111 0000
>>	右移动运算符：把">>"左边的运算数的各二进位全部右移若干位，>> 右边的数字指定了移动的位数	a>>2: 0000 1111

位运算在数据结构的编程题目中也常常出现，通常位运算的算法都是时间和空间复杂度比较占优的一种解法。接下来总结几道leetcode中涉及位运算的解法题目。

leetcode 268. 缺失数字

题目描述：

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。 

示例 1: 
输入: [3,0,1]
输出: 2

示例 2: 
输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明: 
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

大部分人首先想到的是利用散列表来对序列中每个数字进行计数，最后遍历0-n，计数为0的数即为所求。此解法时间复杂度为O(n)，空间复杂度O(n)。

那我们如何做到常数空间复杂度O(1)呢？
这里就要利用到我们的位运算了。如果一个数字出现了两次，则它们的异或^结果为0，我们可以利用这个性质，来对序列中的每个数字求一次异或，再对0-n中的数字求一次异或，则未缺失的数字都出现了两次，而缺失数字只出现了一次，出现两次的数字异或结果都为0，则最后留下的便是我们需要求得的缺失数字。

class Solution:
    def missingNumber(self, nums):
        """
        异或运算，与本身为0。
        :param nums:
        :return:
        """
        res = 0
        for i in range(len(nums)+1):
            res ^= i
        for num in nums:
            res ^= num
        return res

leetcode 260. 只出现一次的数字

题目描述：

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 
找出只出现一次的那两个元素。 

示例 : 
输入: [1,2,1,3,2,5]
输出: [3,5] 

注意： 
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。 
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

题目的难度有所上升了哈，如果我们还是对这个序列中的元素进行异或运算，那最后会得到什么呢？
假如只出现一次的两个元素是 x 和 y，由于其余元素均出现了两次，则其余元素的异或结果最后为0，最后剩下的便是 x 和 y 异或的结果了。我们知道异或运算保留的是两个数字二进制位的差异，有了这个差异我们又能做什么呢？

# 如示例中所述 [1,2,1,3,2,5]
>>> bin(3)
'0b11'
>>> bin(5)
'0b101'
>>> bin(3^5)
'0b110'

我们注意到这个差异中的 1 均来至于 x 或 y，且只能来至于其中一个元素。那我们能否利用这些 1 将 x 和 y 分开呢？答案是肯定的。
分离 x 和 y只需要提取到其中一个 1 便够了。我们定义这个差异为 mask，即 mask = 3^5，那 -mask 是什么呢？——取反再+1。我们通过 mask & (-mask) 来得到 mask 最右边的 1。

>>> mask = 3^5
>>> bin(-mask)
'-0b110'
>>> bin(mask&(-mask))
'0b10'

利用这个 1 将 x 和 y 分离，便得到了最终结果。

class Solution:
    def singleNumber(self, nums):
        """
        位运算
        :param nums:
        :return:
        """
        # 保留出现一次的两个数字的差异
        mask = 0
        for num in nums:
            mask ^= num
        # 记录最右边的1，这个1一定来至于其中一个数字，且只来至于那一个数字。我们可以根据这个1来分离这两个数字
        diff = mask & (-mask)
        res = 0
        for num in nums:
            if diff & num:
                res ^= num
        return [res, mask^res]

leetcode 645. 错误的集合

题目描述：

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个
元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有
一个元素重复。 

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到
重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。 

示例 1: 
输入: nums = [1,2,2,4]
输出: [2,3]

注意:  
给定数组的长度范围是 [2, 10000]。 
给定的数组是无序的。

数组 nums 总共有 n 个元素，其中有一个元素重复。我们对1…n 的数字进行异或运算，再对 nums 中的数字进行异或运算，那结果便只剩下重复元素和丢失元素的差异了，联想到 leetcode 260，再将这两个元素分离，便得到了结果。

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        mask, xor0  = 0, 0
        for idx, num in enumerate(nums, 1):
            mask ^= idx ^ num
        diff = mask & (-mask)
        for idx, num in enumerate(nums, 1):
            if diff & num:
                xor0 ^= num
            if diff & idx:
                xor0 ^= idx
        for num in nums:
            # 即为重复数字
            if num == xor0:
                return [xor0, mask ^ xor0]
        return [mask ^ xor0, xor0]

前面几道题都是讲的异或 ^ 的算法，接下来我们看看这道题该采用什么算法呢？

leetcode 287. 寻找重复数

题目描述：

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），
可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 

示例 1: 
输入: [1,3,4,2,2]
输出: 2

示例 2: 
输入: [3,1,3,4,2]
输出: 3

说明： 
不能更改原数组（假设数组是只读的）。 
只能使用额外的 O(1) 的空间。 
时间复杂度小于 O(n2) 。 
数组中只有一个重复的数字，但它可能不止重复出现一次。

我们知道1 的二进制表示为 0000 0001，若将 1 左移一位，即可得到 0000 0010，其中的数字 1 移动到了第2位；若将 1 左移两位，即可得到 0000 0100，其中的数字 1 移动到了第3位。数组 nums 中的数字都在 1 和 n 之间，若将 1 依次移动 1…n 位，则可得第 2…n+1 位置的 1。为了将每一位的 1 都保留下来，我们可以采用 | 运算。若这个位置的 1 已经被占用了，则表示这个数字为重复数字。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        flag = 0
        for num in nums:
            if flag & (1 << num) > 0:
                return num
            flag |= (1 << num)
        return -1

leetcode 169. 多数元素

题目描述：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 
你可以假设数组是非空的，并且给定的数组总是存在多数元素。 

示例 1: 
输入: [3,2,3]
输出: 3 

示例 2: 
输入: [2,2,1,1,1,2,2]
输出: 2

这道题采用位运算的前提是数组中的元素都为整数。虽然题目没有明确要求，但是位运算算法也能通过测试，所以题目默认应该是整数数组。当然，负数也是有可能的。
在 C 或者 java 语言中，整型占用32字节，而 python 中整型为动态类型，且没有最大值限制。我们这里的解法都是基于整型占用32位的前提下的。

想象数组中每个数字都是由32个位置所组成，每个位置为 0 或者 1。出现次数大于 ⌊n/2⌋ 的这个元素，每个位置出现的 0 或 1 的次数也是大于 ⌊n/2⌋ 的。由于 0 只是占位，1 才能帮助还原数字，所以我们可以统计每个位置 1 出现的次数，如果出现次数大于⌊n/2⌋，则计算到还原数字中。

class Solution:
    def majorityElement(self, nums) -> int:
        """
        位运算 这里应该再加一个前提 数组中的元素为整数 且每个整数占用32字节
        :param nums:
        :return:
        """
        res = 0
        n = len(nums) >> 1
        for i in range(32):
            ones = 0
            # 统计每个位置1出现的次数
            for num in nums:
                # 为了处理出现负数
                ones += (num + 2 ** 31) >> i & 1
            # 如果这个位置1出现的次数满足条件，则是目标数字
            if ones > n:
                res += 1 << i
        return res - 2 ** 31