六十一、深入學(xué)習(xí)位運(yùn)算

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

總結(jié)下之前基礎(chǔ)的內(nèi)容

• & 按位與 將兩個(gè)操作數(shù)對(duì)應(yīng)的每一位進(jìn)行邏輯與操作，滿足：1&1=1，1&0=0，0&1=0，0&0=0，

• | 按位或是將兩個(gè)操作數(shù)對(duì)應(yīng)的每一位進(jìn)行邏輯或操作，滿足：1|0=1，0|1=1，1|1=1，0|0=0，

• ^ 按位異或，將兩個(gè)操作數(shù)對(duì)應(yīng)的每一位進(jìn)行邏輯異或操作，滿足1^1=0，0^0=0，1^0=1，0^1=1

• ~ 按位取反是將單個(gè)操作數(shù)對(duì)應(yīng)的每一位取反，~1=0，~0=1

下面就是這篇博客重點(diǎn)內(nèi)容，總結(jié)于極客時(shí)間的算法面試通過40講的位運(yùn)算的內(nèi)容。

下面就是學(xué)習(xí)記錄的筆記

交換兩數(shù)

交換兩數(shù)如果不想額外的空間消耗，就可以用位運(yùn)算來實(shí)現(xiàn)，這個(gè)是以前不知道的。

>>>?x?=1
>>>?y?=?2
>>>?x?=?x^y
>>>?y?=?x^y
>>>?x?=?x^y
>>>?x
2
>>>?y
1

判斷奇數(shù)和偶數(shù)

x & 1 == 1 or == 0其實(shí)是來判斷奇數(shù)還是偶數(shù)，原理就是按照位“與”運(yùn)算的原則，如果兩個(gè)值相應(yīng)的位置都為1也就是上下都為1的時(shí)候，那么該結(jié)果就是1，如果有一個(gè)不是1，那么就是0。

因?yàn)?& 1這里固定了，二級(jí)制的原因，奇數(shù)那么最后一個(gè)一定是1，偶數(shù)最后一個(gè)一定是0。

>>>?x?=?2?#10?
>>>?y?=?3?#11
>>>?x?&?1
0
>>>?y?&?1
1

因此使用x & 1 == 1 or == 0判斷奇數(shù)或者偶數(shù)和 x%2 == 0等價(jià)。

清除最低位的1

這個(gè)道理和上面的一樣，清除最低位的1就是去掉二級(jí)制的最后一個(gè)。每執(zhí)行一次x = x&(x-1)，會(huì)將x用二進(jìn)制表示時(shí)最右邊的一個(gè)1變?yōu)?，因?yàn)閤-1將會(huì)將該位(x用二進(jìn)制表示時(shí)最右邊的一個(gè)1)變?yōu)?。

>>>?x?=?7
>>>?bin(x)
'0b111'
>>>?x?&?(x-1)
6
>>>?bin(6)
'0b110'
>>>?x?=?x?&?(x-1)
>>>?x?&?(x-1)
4
>>>?bin(4)
'0b100'

x&(-x)

x&(-x)的意思

• 當(dāng)x是一個(gè)偶數(shù)與它的負(fù)值向與時(shí)，結(jié)果是能被這個(gè)偶數(shù)整除的最大的2的n次冪，x&(-x)返回x與2^64的最大公約數(shù)，即x最多能被n個(gè)2整除就返回2^n。

• 當(dāng)x是一個(gè)奇數(shù)與它的負(fù)值向與時(shí)結(jié)果一定是1，則返回得到最低的1

>>>?7?&?-7?#111??7二進(jìn)制最低是1的位數(shù)是1
1
>>>?6?&?-6?#??6與2^64最大公約數(shù)是2
2
>>>?4?&?-4?#?4與2^64最大公約數(shù)是4
4
>>>?8&?-8??#?8與2^64最大公約數(shù)是8
8
>>>?9?&?-9?#?1001
1

文字版：指定位置

• 將 x 最右邊的 n 位清零：x &(~0<
• 獲取 x 的第 n 位值（0或者1）：(x>>n)&1
• 獲取x的第n位的冪值：x&(1<
• 僅將第 n 位置為1：x|(1<
• 僅將第 n 位置為0：x&(~(1<
• 將 x 最高位至第 n 位（含）清零：x&((1<
• 將 第n位 至第 0 位（含）清零：x&(~((1<<(n+1))-1))

還有很多的復(fù)雜的位運(yùn)算，Runsen是小白的水平，真的看不懂怎么多。

下面是嘗試使用

>>>?7&(~0<<2)?#111??將最右邊的2位清零
4?#100
>>>?7&(~0<<1)??#111??將最右邊的1位清零
6?#110
>>>?(2>>5)&1??#101??獲取?5?的第?2?位值
0

Leetcode 191 ：統(tǒng)計(jì)位1的個(gè)數(shù)

編寫一個(gè)函數(shù)，輸入是一個(gè)無符號(hào)整數(shù)（以二進(jìn)制串的形式），返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 '1' 的個(gè)數(shù)（也被稱為漢明重量）。

輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進(jìn)制串?00000000000000000000000000001011 中，共有三位為?'1'。

最快的方法就是轉(zhuǎn)化為字符串的，然后通過遍歷判斷的方式或者count的方法求出1的個(gè)數(shù)。記得需要進(jìn)行bin操作。

class?Solution:
????def?hammingWeight(self,?n:?int)?->?int:
????????index?=?0
????????for?i?in?str(bin(n)):
????????????if?i?==?"1":
????????????????index??=?index?+?1
????????return?index

但是Runsen學(xué)習(xí)的是位運(yùn)算，因此也要學(xué)會(huì)位運(yùn)算的方法。方法也很簡單：每一次右移一位，判斷是 奇數(shù)還是偶數(shù)，奇數(shù)那么就加一，因?yàn)槲粩?shù)最后一個(gè)肯定是1。

class?Solution:
????def?hammingWeight(self,?n:?int)?->?int:
????????count?=?0
????????while?n?!=?0:
????????????#x%2?!=?0等價(jià)
????????????if?n&1?!=?0:
????????????????count?=?count?+?1
????????????n?=?n?>>?1?
????????return?count

在Leetcode上，Runsen也看了一個(gè)官方的最快的解決的方法。就是遍歷數(shù)字的 32 位。如果某一位是 1，將計(jì)數(shù)器加一。其實(shí)就是mask左移一位，比如第一次是0001（這里有32位），那么下一次就是0010。

class?Solution:
????def?hammingWeight(self,?n:?int)?->?int:
????????res?=?0?
????????mask?=?1
????????for?i?in?range(32):
?????????if?n?&?mask:
??????????res?+=1
?????????mask?=?mask?<1
???????return?res??

Leetcode231：2的冪次方問題

給定一個(gè)整數(shù)，編寫一個(gè)函數(shù)來判斷它是否是 2 的冪次方。

輸入:?1
輸出:?true
解釋:?20?=?1

輸入:?16
輸出:?true
解釋:?24?=?16

若，且 為自然數(shù)（即 為 的冪），則一定滿足以下條件：恒有 ，這是為什么，Runsen告訴大家，這是因?yàn)椋?span style="cursor:pointer;">的位運(yùn)算只有一個(gè)1，那么通過 ，把那個(gè)1拔了出來，然后全部都是000000000了。

因此最快的方法就是return n > 0 and n & (n - 1) == 0，還有一種的方法是通過math.log2最后求出來是不是整數(shù)。但是返回的是浮點(diǎn)數(shù)，比如是2.0 。所以這種方法就pass。最后一種就是通過不斷對(duì)2取模運(yùn)算。最后看看是不是1。

class?Solution(object):
????def?isPowerOfTwo(self,?n):
????????"""
????????:type?n:?int
????????:rtype:?bool
????????"""
????????if?n?==?0:
????????????return?False
????????while?n?%?2?==?0:
????????????n?=?n?/?2
????????return?n?==?1

Leetcode338：比特位計(jì)數(shù)問題

給定一個(gè)非負(fù)整數(shù) num。對(duì)于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i ，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。

示例?1:

輸入:?2
輸出:?[0,1,1]
示例?2:

輸入:?5
輸出:?[0,1,1,2,1,2]

最快速的方法就是直接count進(jìn)行計(jì)數(shù)就可以了。

class?Solution:
????def?countBits(self,?num:?int)?->?List[int]:
????????res?=?[]
????????for?i?in?range(num+1):
????????????count?=?bin(i).count("1")
????????????res.append(count)
????????return?res

這題還可以使用位運(yùn)算或者動(dòng)態(tài)規(guī)劃的方法，Runsen的動(dòng)態(tài)規(guī)劃真的是爛到家。

思路：動(dòng)態(tài)規(guī)劃

觀察：
十進(jìn)制0：?二進(jìn)制0
十進(jìn)制1：?二進(jìn)制1
十進(jìn)制2：?二進(jìn)制10
十進(jìn)制3：?二進(jìn)制11
十進(jìn)制4：?二進(jìn)制100
十進(jìn)制5：?二進(jìn)制101

二進(jìn)制中，乘以2相當(dāng)于左移一位，1的個(gè)數(shù)不會(huì)改變；由于偶數(shù)的二進(jìn)制形式結(jié)尾一定是0，所以一個(gè)偶數(shù)加1變?yōu)槠鏀?shù)，只會(huì)將其結(jié)尾的0變?yōu)?；

所以狀態(tài)轉(zhuǎn)移方程為：

$dp(i) = dp(i//2)$ 若i為偶數(shù)；這里//2保證是整數(shù)，防止溢出

$dp(i) = dp(i-1)+1$ 若i為奇數(shù)；

邊界條件：dp(0) = 0

class?Solution:
????def?countBits(self,?num:?int)?->?List[int]:
????????dp?=?[0]?*?(num+1)
????????for?i?in?range(1,num+1):
?????????if?i?%?2?==?0:
??????????dp[i]=dp[i//2]
?????????else:
??????????dp[i]=dp[i-1]+1
????????return?dp

最后說下位運(yùn)算：dp[i] = dp[i>>1] + (i&1)，這里 ?i>>1代表前一個(gè)二進(jìn)制位的次數(shù), ?i&1代表i的末尾是否為1，因此可以繼續(xù)將代碼變得更簡潔。

class?Solution:
????def?countBits(self,?num:?int)?->?List[int]:
????????dp?=?[0]
?????for?i?in?range(1,?num?+?1):
?????????dp.append(dp[i>>1]?+?(i&1))
?????return?dp

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?

Reference