[数据结构与算法]Task06：位运算

1. 视频题目

1.1 只出现一次的数字

1.1.1 描述

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

示例 2:

输入: [4,1,2,1,2]
输出: 4

1.1.2 代码

其实直观的解题或许还是打表，新建一个字典存储数字和出现次数

先遍历原数组统计出现次数，再遍历字典取出出现一次的数字

不过这次练习是位运算，利用位运算的操作，也算直观

一个数字自身异或的结果为零，任何数与零异或还是自身

而且异或这种运算，满足交换律和结合律，这里不再证明

也就是说一个异或序列，会消除所有出现偶数次的数字

也就是说刚好剩下只出现奇数次的数字，在本题就是1次

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        while nums:
            ans = ans^nums.pop()
            
        return ans

1.1.3 总结

一个异或运算的数字序列，会消除所有出现偶数次的数字，保留奇数次数字

1.2 只出现一次的数字 III

1.2.1 描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

1.2.2 代码

直观解题的思路还是打表，新建字典用来存数字和出现次数

如果是要去使用位运算，那思路可能稍微要复杂那么一点

首先起始步骤还是延续上一题的操作，异或整个序列

最终得到的结果，就是只出现一次的两个数字的异或

此时我们回顾异或的定义，对应位不同则为一，就是差异

所以现在我们得到了只出现一次的两个数字的差异

所以我们可以根据这个差异将两个数字分开到两组异或序列

至于其他数字，每两个相同的都会被分进同一个序列消除掉

所以说这两个异或序列最后的结果就是只出现一次的两个数字

还有一点需要注意的就是如何设计校验数字来分离答案的两个数字

我们可以利用&操作，使第一步的异或结果&自身的相反数，取出最右边的1

此时校验数字其他的位置都为0，只有最右边的1那一位为1

接下来就是利用这个校验数字来将答案的两个数字分离到两个序列

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        ans = 0
        for i in nums:
            ans = ans^i
        # 得到只出现一次的两个元素异或的结果
        ans = -ans & ans
        # 取出异或结果最右边的那一位1，用作校验
        ans1 = ans2 = 0
        for i in nums:
            if i&ans==0 :
            # 如果校验位不同
                ans1 ^= i
            else:
            # 如果校验位相同
                ans2 ^= i
        
        return [ans1,ans2]

1.2.3 总结

异或的定义是，对应位不同则为1，就是两者的差异

一个数字&自身的相反数，取出的就是最右边的那个1

也就是这个结果的其他的位置都为0，只有最右边的1那一位为1

2.作业题目

2.1 2的幂

2.1.1 描述

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

提示：

$?2^{31}<=n<=2^{31}?1$

进阶：你能够不使用循环/递归解决此问题吗？

2.1.2 代码

直观来讲还是循环或者递归，在数字比n小的情况下

不断乘以2，直到相等或者比2要大

但是如果按照位运算的角度，就参考上一题的总结

一个数字&自身的相反数，取出的就是最右边的那个1

那如果一个数字是2的幂，那就只有一位是1，即最右边的1

也就是说一个数字&自身的相反数等于他自身，为2的幂

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n==0:
            return False
        else:
            return (n & -n) == n

2.1.3 总结

一个数字&自身的相反数等于他自身，则该数字为2的幂

2.2 只出现一次的数字 II

2.2.1 描述

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

2.2.2 代码

直接一点的做法还是打表，统计次数，然后过滤出来答案

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        freq = collections.Counter(nums)
        ans = [num for num, occ in freq.items() if occ == 1][0]
        return ans

如果使用位运算，那就要将这些数字都视作是二进制数，以下遵循这个前提

对于这组数字的每一位，如果和为3的倍数，就证明答案的这一位为0，反之为1

取[0,1,0,1,0,1,99]作题中给出的整数数组，这里以最后一位为例子简要说明

0的最后一位为0，出现3次，1的最后一位为1，出现三次，99的最后一位为1，出现一次

所以，这组数字的最后一位的和，为4，不是3的整数倍，其对3取余的余数为1

也就是说，答案的这个数字，在最后一位的值为1；如果余数为零，则答案的这一位也为0

需要注意的是，如果使用的语言对「有符号整数类型」和「无符号整数类型」没有区分，那么可能会得到错误的答案。这是因为「有符号整数类型」（即 int类型）的第 31个二进制位（即最高位）是补码意义下的符号位，对应着 $?2^{31}$ ，而「无符号整数类型」由于没有符号，第 31个二进制位对应着$2^{31}$ 。因此在某些语言（例如 Python）中需要对最高位进行特殊判断。

class Solution:
    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.2.3 总结

这里主要需要注意的就是python是无符号类型的，所以在最高位可能出现错误¹

以上 Python 代码与 C# 代码逻辑完全一致，但提交时报错。错误信息如下：
?

输入：[-2,-2,1,1,-3,1,-3,-3,-4,-2]
输出：4294967292
预期结果：-4

?
我们发现：
?

-4 补码为 1111 1111 1111 1111 1111 1111 1111 1100

?
如果不考虑符号位
?

1111 1111 1111 1111 1111 1111 1111 1100 -> 4294967292 

?
是不是很坑，C++，C#，Java等语言的整型是限制长度的，如：byte 8位，int 32位，long 64位，但 Python 的整型是不限制长度的（即不存在高位溢出），所以，当输出是负数的时候，会导致认为是正数！因为它把32位有符号整型认为成了无符号整型，真是坑。
?
我们对以上的代码进行修改，加入判断条件if result > 2 ** 31-1
意即超过32位整型的范围就表示负数了result -= 2 ** 32，即可得到对应的负数。

还有更加进阶的方法，时间有限，以后再说²、³、⁴

2.3 子集

2.3.1 描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

2.3.2 代码

2.3.3 总结