六十、走進(jìn)位運(yùn)算的大門(mén)

「@Author：Runsen」

?

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

?

根據(jù)我的腦海大綱，現(xiàn)在應(yīng)該進(jìn)入位運(yùn)算的大門(mén)。

位運(yùn)算，計(jì)算機(jī)內(nèi)所有的數(shù)都以二進(jìn)制存儲(chǔ)，位運(yùn)算是對(duì)二進(jìn)制位的操作。

按位“與”運(yùn)算

按位“與”運(yùn)算的運(yùn)算符是：&。首先我聲明一個(gè)變量i等于11，j等于2，然后我們計(jì)算i和j的按位“與”運(yùn)算，也就是11&2，得到的結(jié)果是2.‘

個(gè)2是怎么來(lái)的，首先我們要把這個(gè)11和這個(gè)2全部轉(zhuǎn)換成二進(jìn)制，我們從上圖看出11的二進(jìn)制是0b1011，2的二進(jìn)制是0b10。0b這個(gè)它就是一個(gè)二進(jìn)制的標(biāo)識(shí)位，就是告訴我們這個(gè)是二進(jìn)制。

按照位“與”運(yùn)算的原則，如果兩個(gè)值相應(yīng)的位置都為1也就是上下都為1的時(shí)候，那么該結(jié)果就是1，如果有一個(gè)不是1，那么就是0

1011
0010
----
0010

所以，1011和0010的按位“與”運(yùn)算就是0010,然后將二進(jìn)制的0010轉(zhuǎn)化為十進(jìn)制，就是我們的結(jié)果2。

按位“或”運(yùn)算

下面，我們介紹按位“或”運(yùn)算。按位“或”運(yùn)算的運(yùn)算符是：|。我們同樣計(jì)算11和2的按位“或”運(yùn)算，得到的結(jié)果是11。

這個(gè)結(jié)果2到底是怎么樣來(lái)進(jìn)行運(yùn)算的？11的二進(jìn)制是1011，而2的二進(jìn)制是0010。

按照位“或”運(yùn)算的原則，如果兩個(gè)值相應(yīng)的位置有一個(gè)是1,那么該結(jié)果就是1，也就是如果都是0，該結(jié)果就是0

1011
0010
----
1011

所以，1011和0010的按位“與”運(yùn)算就是1011,然后將二進(jìn)制的1011轉(zhuǎn)化為十進(jìn)制，就是我們的結(jié)果11。

按位“異或”運(yùn)算

下面，我們介紹按位“異或”運(yùn)算。按位“異或”運(yùn)算的運(yùn)算符是：^。我們同樣計(jì)算11和2的 按位“異或”運(yùn)算，得到的結(jié)果是9。

這個(gè)結(jié)果9到底是怎么樣來(lái)進(jìn)行運(yùn)算的？11的二進(jìn)制是1011，而2的二進(jìn)制是0010。

按位“異或”運(yùn)算的原則，如果兩個(gè)值相應(yīng)的位置相同1,那么該結(jié)果就是0，也就是如果都是0或者都是1，該結(jié)果就是0.同樣只有是1和0，那些結(jié)果就是1

1011
0010
----
1001

所以，1011和0010的按位“異或”運(yùn)算就是1001,然后將二進(jìn)制的1001轉(zhuǎn)化為十進(jìn)制，就是我們的結(jié)果9。

按位取反運(yùn)算

下面，我們介紹按位取反運(yùn)算。按位“異或”運(yùn)算的運(yùn)算符是：~。我們計(jì)算11的按位取反運(yùn)算，得到的結(jié)果是-12。

這個(gè)結(jié)果-12到底是怎么樣來(lái)進(jìn)行運(yùn)算的？按位取反的計(jì)算結(jié)論是：~n = -(n+1)

因此，11的按位取反運(yùn)算 ：~11=-(11+1)=-12

左移運(yùn)算符

下面，我們介紹左移運(yùn)算符。左移運(yùn)算符是：<<。我們計(jì)算11的左移2位的運(yùn)算，得到的結(jié)果是44。

這個(gè)結(jié)果44到底是怎么樣來(lái)進(jìn)行運(yùn)算的？左移2位，就是1011往左移動(dòng)2位，然后用0來(lái)補(bǔ)充，變成了101100。本來(lái)在這里向左邊移動(dòng)，其實(shí)是后邊舍棄掉2位

1011
----
101

所以，1011的右移2位的運(yùn)算就是101100,然后將二進(jìn)制的101100轉(zhuǎn)化為十進(jìn)制，就是我們的結(jié)果44。

右移運(yùn)算符

下面，我們介紹右移運(yùn)算符。右移運(yùn)算符是：>>。我們計(jì)算11的右移2位的運(yùn)算，得到的結(jié)果是2。

這個(gè)結(jié)果2到底是怎么樣來(lái)進(jìn)行運(yùn)算的？右移2位，就是1011往右移動(dòng)2位，然后右邊的11直接去除，變成了10。本來(lái)在這里向右邊移動(dòng)，其實(shí)是后邊刪除位數(shù)。

1011
----
10

所以，1011和的左移2位的運(yùn)算就是10,然后將二進(jìn)制的10轉(zhuǎn)化為十進(jìn)制，就是我們的結(jié)果2。下表就是總結(jié)。

判斷奇數(shù)還是偶數(shù)

通常判斷奇數(shù)還是偶數(shù)我們想到的辦法就是除以2，看余數(shù)是否為0。具體Python代碼如下：

def?isodd(x):
????return?True?if?(x?%?2?==?0)?else?False

那么如何使用位運(yùn)算呢？

我們只需要使用&運(yùn)算，與1進(jìn)行&，如果為1，那么該數(shù)為奇數(shù)；如果為0，那么該數(shù)是偶數(shù)，具體Python代碼如下：

def?isodd(x):
????return?True?if?(x?&?1)?else?False

左移一位相當(dāng)于乘以2，右移一位相當(dāng)于除以2

在面試的過(guò)程中，通常會(huì)遇到的一個(gè)問(wèn)題是寫(xiě)二分查找代碼。

Python二分查找的代碼如下：

def?binary_search(list,?item):
????'''
????:param?list:?有序列表
????:param?item:?要查找的元素
????:return:?item在list中的索引，若不在list中返回None
????'''
????low?=?0
????high?=?len(list)?-?1
????while?low?<=?high:
????????mid?=?(low?+?high)?//?2
????????if?list[mid]?==?item:
????????????return?mid
????????elif?list[mid]?????????????low?=?mid?+?1
????????elif?list[mid]?>?item:
????????????high?=?mid?-?1
????return?None

其中有一步是需要取最小下標(biāo)和最大下標(biāo)的中間值，若使用位運(yùn)算符，則變成midpoint = (low + high) >> 1，面試官肯定會(huì)對(duì)你刮目相看。

下面就是位運(yùn)算常見(jiàn)用法總結(jié)

「判斷x的奇偶數(shù)」

x?%?2?==?1?//?常規(guī)寫(xiě)法
x?&?1?==?1?//?為真奇數(shù)，為假偶數(shù)

「計(jì)算中位數(shù)」

mid?=?(left?+?right)?/?2??//?常規(guī)寫(xiě)法
mid??=?(left?+?right)?>>?1?//?位運(yùn)算

LeetCode 第 78題：子集

下面，我們來(lái)看一題關(guān)于二進(jìn)制的Leetcode。題目很簡(jiǎn)單，就是給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）

#給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。?
#?說(shuō)明：解集不能包含重復(fù)的子集。?
#?示例:?
#?輸入:?nums?=?[1,2,3]
#輸出:
#[
#??[3],
#??[1],
#??[2],
#??[1,2,3],
#??[1,3],
#??[2,3],
#??[1,2],
#??[]
#]?
#?Related?Topics?位運(yùn)算?數(shù)組?回溯算法

既然這道題讓我們求的是所有的子集，那么我們可以從子集的特點(diǎn)入手。假如整數(shù)數(shù)組的長(zhǎng)度是3，那么子集有8個(gè)。整數(shù)數(shù)組的長(zhǎng)度是4，那么子集有16個(gè)。

一個(gè)含有n個(gè)元素的子集的數(shù)量是，這個(gè)是高中數(shù)學(xué)中的集合的數(shù)學(xué)題，不知道的可能忘得一干二凈。

這題非常巧妙地使用二進(jìn)制的位運(yùn)算。使用位運(yùn)算，對(duì)每一位為1的表示這一位的數(shù)字存在，求[1,2,3] 的子集，我們可以用0和1表示有和無(wú)。比如編碼001，表示只含有3，編碼101，表示含有1,3。編碼111表示1,2,3。

因?yàn)槊總€(gè)數(shù)只有選與不選兩種情況，具體的情況如下所示。

具體的Python代碼。

class?Solution:
????def?subsets(self,?nums:?List[int])?->?List[List[int]]:
????????ret?=?[]
????????n?=?len(nums)
????????#?遍歷所有的狀態(tài)
????????#?二進(jìn)制的巧用：1左移n位相當(dāng)于2的n次方，也可以寫(xiě)成2**n
????????for?s?in?range(1?<????????????cur?=?[]
????????????#?通過(guò)位運(yùn)算找到每一位是0還是1
????????????for?i?in?range(n):
????????????????#?判斷s狀態(tài)在2的i次方上，也就是第i位上是0還是1
????????????????if?s?&?(1?<????????????????????cur.append(nums[i])
????????????ret.append(cur[:])
????????return?ret

其實(shí)位運(yùn)算說(shuō)簡(jiǎn)單，也很簡(jiǎn)單，但有的時(shí)候要用，我卻怎么也想不到，主要是因?yàn)槠孑夂芏唷?/p>

在此題中，還有一種方法是回溯算法，注意需要將空集的情況添加。

class?Solution:
????def?subsets(self,?nums:?List[int])?->?List[List[int]]:
????????res?=?[[]]
????????for?i?in?nums:
????????????res?=?res?+?[[i]?+?num?for?num?in?res]
????????return?res

?

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

?

Reference