知識(shí)點(diǎn)
1. 概念
按位運(yùn)算符是把數(shù)字看作二進(jìn)制來(lái)進(jìn)行計(jì)算的
2.操作
非操作 ~：把num的補(bǔ)碼中的0和1全部取反（0變1,1變0）链方，且符號(hào)也取反
與操作&：兩個(gè)對(duì)應(yīng)位都為1時(shí)才為1
或操作 |: 兩個(gè)對(duì)應(yīng)位中有一個(gè)1就為1
異或操作 ^ ：不同時(shí)為1阶剑，相同時(shí)為0；滿足交換律和結(jié)合律
按位左移操作<<：向左移動(dòng)i位所得到的值，右移為>>
題目
1. 只出現(xiàn)一次的數(shù)字
需要線性時(shí)間復(fù)雜度和不用額外空間灭衷；集合哼绑、哈希表存儲(chǔ)都需要O(n)的空間。需要使用位運(yùn)算
對(duì)于這道題倒淫，可使用異或運(yùn)算 ⊕伙菊。異或運(yùn)算有以下三個(gè)性質(zhì)。
- 任何數(shù)和 0 做異或運(yùn)算敌土，結(jié)果仍然是原來(lái)的數(shù)镜硕，即 a⊕0=a。
- 任何數(shù)和其自身做異或運(yùn)算返干，結(jié)果是 0兴枯，即 a⊕a=0。
- 異或運(yùn)算滿足交換律和結(jié)合律矩欠，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b财剖。
可推導(dǎo)為
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x, y: x ^ y, nums)
這里reduce 函數(shù)將一個(gè)數(shù)據(jù)集合(鏈表，元組等)中的所有數(shù)據(jù)進(jìn)行下列操作癌淮，用傳給 reduce 中的函數(shù) function(有兩個(gè)參數(shù))先對(duì)集合中的第 1躺坟、2 個(gè)元素進(jìn)行操作，得到的結(jié)果再與第三個(gè)數(shù)據(jù)用 function 函數(shù)運(yùn)算该默，最后得到一個(gè)結(jié)果瞳氓。
reduce([function], sequence, initial)
異或解法：異或運(yùn)算滿足交換律，aba=aab=b,因此ans相當(dāng)于nums[0]nums[1]nums[2]nums[3]nums[4]..... 然后再根據(jù)交換律把相等的合并到一塊兒進(jìn)行異或（結(jié)果為0）栓袖，然后再與只出現(xiàn)過(guò)一次的元素進(jìn)行異或匣摘，這樣最后的結(jié)果就是，只出現(xiàn)過(guò)一次的元素（0^任意值=任意值）
2. 只出現(xiàn)一次的數(shù)字 Ⅱ
二進(jìn)制位思路：
答案的第 ii 個(gè)二進(jìn)制位就是數(shù)組中所有元素的第 ii 個(gè)二進(jìn)制位之和除以 33 的余數(shù)裹刮。
為了方便敘述音榜，我們稱「只出現(xiàn)了一次的元素」為「答案」。
由于數(shù)組中的元素都在 int（即 3232 位整數(shù)）范圍內(nèi)捧弃，因此我們可以依次計(jì)算答案的每一個(gè)二進(jìn)制位是 0 還是 1赠叼。
具體地擦囊，考慮答案的第 i 個(gè)二進(jìn)制位（ii 從 00 開(kāi)始編號(hào)），它可能為 0 或 1嘴办。對(duì)于數(shù)組中非答案的元素瞬场，每一個(gè)元素都出現(xiàn)了 3 次，對(duì)應(yīng)著第 ii 個(gè)二進(jìn)制位的 3 個(gè) 0 或 3 個(gè) 1涧郊，無(wú)論是哪一種情況贯被，它們的和都是 3 的倍數(shù)（即和為 0 或 3）。
因此妆艘，統(tǒng)計(jì)所有數(shù)字的各二進(jìn)制位中 1 的出現(xiàn)次數(shù)彤灶，并對(duì) 3求余，結(jié)果則為只出現(xiàn)一次的數(shù)字批旺。
3. 2的冪
可知n的二進(jìn)制位幌陕，最高位為1，其他為0
且n?1 二進(jìn)制最高位為 0汽煮，其余所有位為 1搏熄；
則n與n-1的與運(yùn)算則一直為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
