知识点
1. 概念
按位运算符是把数字看作二进制来进行计算的
2.操作
非操作 ~：把num的补码中的0和1全部取反（0变1,1变0），且符号也取反
与操作&：两个对应位都为1时才为1
或操作 |: 两个对应位中有一个1就为1
异或操作 ^ ：不同时为1，相同时为0；满足交换律和结合律
按位左移操作<<：向左移动i位所得到的值，右移为>>
题目
1. 只出现一次的数字
需要线性时间复杂度和不用额外空间；集合、哈希表存储都需要O(n)的空间。需要使用位运算
对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
- 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
- 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
可推导为
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x, y: x ^ y, nums)
这里reduce 函数将一个数据集合(链表，元组等)中的所有数据进行下列操作，用传给 reduce 中的函数 function(有两个参数)先对集合中的第 1、2 个元素进行操作，得到的结果再与第三个数据用 function 函数运算，最后得到一个结果。
reduce([function], sequence, initial)
异或解法：异或运算满足交换律，aba=aab=b,因此ans相当于nums[0]nums[1]nums[2]nums[3]nums[4]..... 然后再根据交换律把相等的合并到一块儿进行异或（结果为0），然后再与只出现过一次的元素进行异或，这样最后的结果就是，只出现过一次的元素（0^任意值=任意值）
2. 只出现一次的数字 Ⅱ
二进制位思路：
答案的第 ii 个二进制位就是数组中所有元素的第 ii 个二进制位之和除以 33 的余数。
为了方便叙述，我们称「只出现了一次的元素」为「答案」。
由于数组中的元素都在 int（即 3232 位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 0 还是 1。
具体地，考虑答案的第 i 个二进制位（ii 从 00 开始编号），它可能为 0 或 1。对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 ii 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3求余，结果则为只出现一次的数字。
3. 2的幂
可知n的二进制位，最高位为1，其他为0
且n−1 二进制最高位为 0，其余所有位为 1；
则n与n-1的与运算则一直为1
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and n & (n - 1) == 0
4. 子集
回溯
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def helper(i, tmp):
res.append(tmp)
for j in range(i, n):
helper(j + 1,tmp + [nums[j]] )
helper(0, [])
return res
