按位操作是真的復(fù)雜，且技巧性很高，特此專(zhuān)門(mén)開(kāi)一篇，來(lái)簡(jiǎn)單講解。
- 目錄：
算法：附錄
算法（1）：遞歸
算法（2）：鏈表
算法（3）：數(shù)組
算法（4）：字符串
算法（5）：二叉樹(shù)
算法（6）：二叉查找樹(shù)
算法（7）：隊(duì)列和堆棧（附贈(zèng)BFS和DFS）
算法（8）：動(dòng)態(tài)規(guī)劃
算法（9）：哈希表
算法（10）：排序
算法（11）：回溯法
算法（12）：位操作
1. 原碼
原碼就是符號(hào)位加上真值的絕對(duì)值, 即用第一位表示符號(hào), 其余位表示值. 比如如果是8位二進(jìn)制:
[+1]原 = 0000 0001
[-1]原 = 1000 0001
第一位是符號(hào)位. 因?yàn)榈谝晃皇欠?hào)位, 所以8位二進(jìn)制數(shù)的取值范圍就是[-127 , 127]心例，即:
[1111 1111 , 0111 1111]
2. 反碼
反碼的表示方法是:
正數(shù)的反碼是其本身
負(fù)數(shù)的反碼是在其原碼的基礎(chǔ)上, 符號(hào)位不變瑟俭，其余各個(gè)位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
3. 補(bǔ)碼
補(bǔ)碼的表示方法是:
正數(shù)的補(bǔ)碼就是其本身
負(fù)數(shù)的補(bǔ)碼是在其原碼的基礎(chǔ)上, 符號(hào)位不變, 其余各位取反, 最后+1. (即在反碼的基礎(chǔ)上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]補(bǔ)
[-1] = [10000001]原 = [11111110]反 = [11111111]補(bǔ)
??計(jì)算機(jī)儲(chǔ)存數(shù)據(jù)都是用補(bǔ)碼的方式儲(chǔ)存的，c++里面獲取某個(gè)數(shù)的二進(jìn)制表示(也就是補(bǔ)碼)如下：cout << bitset<sizeof(int) *8> (num) << endl;
例題1： 計(jì)算一個(gè)數(shù)轉(zhuǎn)化為2進(jìn)制之后契邀，包含多少1摆寄。（ 又稱(chēng)之為 Hamming weight，漢明重量）
輸入：5
輸出：2（0101）
解釋?zhuān)?br>
n = n & (n-1)可以消除二進(jìn)制位最右邊的一個(gè)1坯门。
如：0101 & 0100微饥，結(jié)果為 0100， 和 0101相比古戴，第四位的1消失了欠橘，計(jì)數(shù)器加1；
再繼續(xù)0100 & 0011现恼，結(jié)果為 0000肃续， 和0100相比，第二位的1消失了叉袍，計(jì)數(shù)器加1始锚；
此時(shí)n=0，跳出循環(huán)喳逛。
def solution(n):
count = 0
while n:
n = n & (n-1)
count += 1
return count
ans = solution(15)
print(ans)
例題2：判斷一個(gè)數(shù)是否為2的指數(shù)冪瞧捌。
輸入：8
輸出：True
解釋?zhuān)?br>
1的二進(jìn)制為1
2的二進(jìn)制為10
4的二進(jìn)制為100
8的二進(jìn)制為1000
發(fā)現(xiàn)只有最高位為1其余位為0，如果將其減一的話那么最高位為0其余位則為1，兩者相與的結(jié)果則必定為0
結(jié)論：如果 a&(a-1) == 0 則a必定是2的指數(shù)冪
def solution(n):
return (n & (n - 1)) == 0
ans = solution(16)
print(ans)
例題3：判斷一個(gè)數(shù)是否為4的指數(shù)冪姐呐。
輸入：16
輸出：True
解釋?zhuān)?br>
1的二進(jìn)制為1
4的二進(jìn)制為100
16的二進(jìn)制為10000
第一句不多說(shuō)殿怜，(num & (num - 1)) == 0用來(lái)判斷是不是2的指數(shù)冪，第二句則是去除掉是2的指數(shù)冪曙砂，但不是4的指數(shù)冪的部分头谜。
def solution(num):
return (num & (num - 1)) == 0 and (num - 1) % 3 == 0
#或者下面這種寫(xiě)法也行
# return (n&(n-1)) == 0 and n & 0x55555555
ans = solution(16)
print(ans)
例題4：兩整數(shù)求和。
輸入：-1鸠澈，1
輸出：0
解釋?zhuān)?br>
下面代碼中 a 儲(chǔ)存不包含進(jìn)位的計(jì)算結(jié)果柱告，即(a ^ b)；
b 只儲(chǔ)存進(jìn)位的結(jié)果款侵，即(a & b) << 1)；
當(dāng)b等于0時(shí)侧纯，代表沒(méi)有進(jìn)位新锈，跳出循環(huán)。
至于mask的作用眶熬，因?yàn)槔碚撋?python 里 int 類(lèi)型的位數(shù)是沒(méi)有上限的妹笆，不同與c++，int為32位娜氏。而最后一句的~(a ^ mask)拳缠，其實(shí)在二進(jìn)制位上，執(zhí)行前后是的結(jié)果是一樣的贸弥，但表達(dá)含義變化了窟坐，將第一位變?yōu)榱朔?hào)位。
如 4294967276（大于2的31次方）绵疲，其二進(jìn)制表示為：
...11111111111111111111111111101100（...表示前面還有很多位哲鸳，因?yàn)?int 類(lèi)型的位數(shù)是沒(méi)有上限），
a ^ mask得：
00000000000000000000000000010011（此時(shí)前面的都mask掉了盔憨，第一位為符號(hào)位徙菠，該數(shù)為19）
再^求反得：
11111111111111111111111111101100（和4294967276的二進(jìn)制完全相同，但是含義變成了-20）
class Solution:
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
# 32 bits integer max
MAX = 0x7FFFFFFF
# 32 bits interger min
MIN = 0x80000000
# mask to get last 32 bits
mask = 0xFFFFFFFF
while b != 0:
# ^ get different bits and & gets double 1s, << moves carry
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
# if a is negative, get a's 32 bits complement positive first
# then get 32-bit positive's Python complement negative
return a if a <= MAX else ~(a ^ mask)
例題5：缺失的數(shù)字
給一個(gè)長(zhǎng)度為n的數(shù)組郁岩，里面存放從0到n的數(shù)婿奔，但是少了一個(gè)，求出該數(shù)问慎。
輸入：[0萍摊，1，2如叼，4记餐，5]
輸出：3
解釋?zhuān)簩?duì)0和某一個(gè)數(shù)進(jìn)行異或操作，則結(jié)果為該數(shù)薇正；
某個(gè)數(shù)對(duì)另一個(gè)數(shù)進(jìn)行兩次 ^異或操作片酝，則結(jié)果還是該數(shù)本身囚衔。
def solution(arr):
ans = 0
for i,num in enumerate(arr):
ans ^= num
ans ^= i
return ans^len(arr)
ans = solution([0,1,2,4,5])
print(ans)
例題6：將一個(gè)32位無(wú)符號(hào)整數(shù)，進(jìn)行按位翻轉(zhuǎn)
輸入：12
輸出：805306368
解釋?zhuān)?br>
00000000000000000000000000001100 （12的32進(jìn)制表示）
00110000000000000000000000000000 （805306368的32進(jìn)制表示）
def solution(n):
ans = 0
mask = 1<<31
while n:
if n&1:
ans |= mask
mask >>= 1
n>>= 1
return ans
n = 12
print(bin(n)[2:].zfill(32))
ans = solution(n)
print(bin(ans)[2:].zfill(32))
例題7：逐個(gè)元素進(jìn)行and 操作雕沿。給出一個(gè)區(qū)間[m, n]练湿，且 0 <= m <= n <= 2147483647，對(duì)m到n之間的每個(gè)元素進(jìn)行與操作审轮，返回操作的結(jié)果肥哎。
輸入：[5,7]
輸出：4 （101 &110 & 111）
解釋?zhuān)簩?和7一直左移，并不斷判斷左移后兩個(gè)數(shù)是否相等疾渣，如果相等（此時(shí)已經(jīng)左移兩次篡诽，1==1），則跳出循環(huán)榴捡，然后右移相同位數(shù)（兩位）杈女，并返回結(jié)果，即4吊圾。
def solution(m,n):
a = 0
while m!=n:
m>>=1
n>>=1
a += 1
return m<<a
ans = solution(5,7)
print(ans)
多運(yùn)算符混合應(yīng)用題目
例題8： DNA重復(fù)序列达椰。某DNA序列由ACGT四個(gè)字母組成，需要找出里面所有長(zhǎng)度為10项乒，且出現(xiàn)重復(fù)的序列啰劲。
輸入：'AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT'
輸出：['AAAAACCCCC', 'CCCCCAAAAA']
輸入：’AAAAAAAAAAA'
輸出：['AAAAAAAAAA']
附注：注意里面的運(yùn)算優(yōu)先級(jí)，首先 +/-優(yōu)先級(jí)最大檀何，其次<< 蝇裤， 隨后是 &，| 的優(yōu)先級(jí)最小频鉴。
def solution(s):
d = {}
ans = []
num = 0
if len(s)<11: return []
for i in range(9):
num = num<<3 | ord(s[i]) - ord('A')+1 & 7
# 上面相當(dāng)于 num = (num<<3) | ((ord(s[i]) - ord('A')+1) & 7)
for i in range(9,len(s)):
num = num << 3 & 0x3fffffff | (ord(s[i]) - ord('A')+1) & 7
if d.get(num) == 1:
ans.append(s[i-9:i+1])
d[num]=d.get(num,0)+1
return ans
ans = solution('AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT')
print(ans)
例題9：單獨(dú)數(shù)字猖辫。給出一個(gè)數(shù)組，該數(shù)組中有兩個(gè)元素只出現(xiàn)一次砚殿，其他的都出現(xiàn)兩次啃憎，請(qǐng)找出這兩個(gè)元素。
輸入：[1,1,2,2,3,4]
輸出：[3,4]
解釋?zhuān)旱谝徊剿蒲祝瑢?duì)所有元素進(jìn)行異或操作辛萍，某一位出現(xiàn)1的次數(shù)為奇數(shù)次，才會(huì)為1羡藐；
第二步贩毕，bit = bit & ~(bit - 1)，找出最右邊第一位為1的二進(jìn)制位仆嗦，其余全置零辉阶。
（eg：bit = 101100，執(zhí)行完之后，bit = 000100）谆甜；
第三步垃僚，再次遍歷數(shù)組，通過(guò)該比特位將數(shù)據(jù)分為兩部分规辱，這兩部分各包含一個(gè)只出現(xiàn)一次的元素谆棺，以及若干個(gè)成對(duì)出現(xiàn)的元素。
def solution(arr):
bit = 0
for i in arr:
bit ^=i
bit = bit & ~(bit - 1)
ans =[0,0]
for i in arr:
if bit & i:
ans[0]^=i
else:
ans[1]^=i
return ans
ans = solution([1,2,3,5,1,3])
print(ans)
例題10：單獨(dú)數(shù)字罕袋。給一個(gè)數(shù)組改淑，其中只有一個(gè)元素出現(xiàn)一次，其他都出現(xiàn)了三次浴讯，找出該元素朵夏。
輸入：[1,1,1,3,4,4,4]
輸出：3
解釋?zhuān)海ù祟}解法通用性很強(qiáng)，題目可以改成：一個(gè)元素出現(xiàn)m次榆纽，其他元素都出現(xiàn)了k次仰猖，只要m不為k的整數(shù)倍即可用該題方法來(lái)求解。）
def solution(arr):
barr = [0] * 32
for n in arr:
for i in range(0, 32):
if n & (1 << i):
barr[i] = (barr[i] + 1) % 3
ans = 0
for i in range(0, 32):
ans = ans | barr[i] << i
return ans if ans <= 0x7fffffff else ~(ans ^ 0xffffffff)
ans = solution([1,1,1,-3])
print(ans)
例題11：單詞長(zhǎng)度的乘積掠河。給定一個(gè)包含各種單詞的數(shù)組亮元，返回一個(gè)最大值猛计，該最大值為：兩個(gè)不含相同字符的單詞唠摹，其長(zhǎng)度的乘積最大值（即len(word[i]) * len(word[j])） 。
輸入：["a","ab","abc","d","cd","bcd","abcd"]
輸出：4 （ len('ab') * len('cd') = 4）
輸入: ["a","aa","aaa","aaaa"]
輸出: 0 （找不到滿足條件的一對(duì)單詞）
def maxProduct(words) :
mask = [0] * len(words)
ans = 0
for i in range(len(words)):
for c in words[i]:
mask[i] |= 1 << ord(c) - ord('a')
for j in range(i):
if not mask[i] & mask[j]:
ans = max(ans, len(words[i]) * len(words[j]))
return ans
ans = maxProduct(["abcw","baz","foo","bar","xtfn","abcdef"])
print(ans)
例題12： 求一個(gè)集合所有子集奉瘤。(這應(yīng)該是最后一題了勾拉，，盗温，)
輸入：[2,3,5]
輸出：[[], [2], [3], [2, 3], [5], [2, 5], [3, 5], [2, 3, 5]]
解釋?zhuān)?br>
對(duì)于集合當(dāng)中每個(gè)數(shù)字藕赞，都有要、不要兩種選擇卖局，所以子集個(gè)數(shù)為 2的len(arr)次方 （即下面的 size）斧蜕。
注意下面的關(guān)鍵句if (1 << j & i)，該句子可以實(shí)現(xiàn)如下取舍方式：
對(duì)于第一個(gè)數(shù)砚偶，1 << j = 1, 二進(jìn)制為0001批销，與 i 進(jìn)行按位與操作后，其取舍方式為：
0染坯，1均芽，0，1单鹿，0掀宋，1，0，1...
對(duì)于第二個(gè)數(shù)劲妙，1 << j = 2, 二進(jìn)制為0010湃鹊，與 i 進(jìn)行按位與操作后，其取舍方式為：
0是趴，0涛舍，1，1唆途，0富雅，0，1肛搬，1...
對(duì)于第三個(gè)數(shù)没佑，1 << j = 4, 二進(jìn)制為0100，與 i 進(jìn)行按位與操作后温赔，其取舍方式為：
0蛤奢，0，0陶贼，0啤贩，1，1拜秧，1痹屹，1...
def solution(arr):
size = 1 << len(arr)
print(size)
ans = [[] for i in range(size)]
for i in range(len(ans)):
for j in range(len(arr)):
if (1 << j & i):
ans[i].append(arr[j])
return ans
ans = solution([2,3,5])
print(ans)
暫且完結(jié)，撒花~~~
