前言

位運(yùn)算的性能大家想必是清楚的，效率絕對(duì)高。相信愛(ài)好源碼的同學(xué)，在學(xué)習(xí)閱讀源碼的過(guò)程中會(huì)發(fā)現(xiàn)不少源碼使用了位運(yùn)算。但是為啥在實(shí)際編程過(guò)程中應(yīng)用少呢？想必最大的原因，是較為難懂。不過(guò)，在面試的過(guò)程中，在手寫(xiě)代碼過(guò)程中，寫(xiě)出一兩個(gè)位運(yùn)算的代碼，還會(huì)讓面試官眼前一亮的。

位運(yùn)算常用的運(yùn)算符包括&（按位與）， | （按位或），~（按位非），^（按位異或），<< (有符號(hào)左移位) ，>>（有符號(hào)右移位）。

下面用幾個(gè)例子說(shuō)明其應(yīng)用，希望對(duì)你有所啟發(fā)。

1、判斷奇數(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

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

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

二分查找的代碼如下：

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

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

3、交換兩個(gè)數(shù)值

數(shù)值交換的代碼相信大家都非常熟悉了，因?yàn)樗坪跏菑膶W(xué)編程語(yǔ)言的最開(kāi)始就一直用：

temp = b
b = a
a = temp

但是怎么使用位運(yùn)算來(lái)完成此功能呢？

a ^= b
b ^= a
a ^= b

確實(shí)比較難理解，原理是什么呢？

第一行，a = a ^ b，很容易理解；

第二行， b = b ^ a = b ^ a ^ b，由于 b ^ b = 0，所以 b = a ^ 0，即 b = a;

第三行， a = a ^ b ,由于a在第一步重新賦值，所以，a = a ^ b ^ a = b，完成了數(shù)值交換。

這里，總結(jié)下異或運(yùn)算的特性：任意數(shù)和自身異或結(jié)果為0；0和任意數(shù)異或結(jié)果還是其本身。

4、尋找數(shù)據(jù)列表中的獨(dú)一無(wú)二

有一個(gè)數(shù)據(jù)列表（2N+1個(gè)整數(shù)），只有一個(gè)數(shù)出現(xiàn)了1次，其余N個(gè)數(shù)都出現(xiàn)了2次。如何找到這個(gè)獨(dú)一無(wú)二的數(shù)據(jù)？

看到這個(gè)題目，相信大家第一次想到的算法肯定是計(jì)數(shù)，建立列表，循環(huán)整個(gè)數(shù)據(jù)并計(jì)數(shù)，然后遍歷這個(gè)列表找到出現(xiàn)次數(shù)為1的數(shù)據(jù)。

這樣，空間復(fù)雜度為O（N）。

如何降低空間復(fù)雜度呢？

注意看一下剛剛講過(guò)的異或的特性：任意數(shù)和自身異或結(jié)果為0；0和任意數(shù)異或結(jié)果還是其本身。

那么，出現(xiàn)了2次的N個(gè)數(shù)異或的結(jié)果是0，再與出現(xiàn)次數(shù)為1次的數(shù)異或的結(jié)果即為該數(shù)。即：找到這個(gè)獨(dú)一無(wú)二數(shù)據(jù)的辦法是通過(guò)對(duì)全部的數(shù)據(jù)進(jìn)行異或操作，空間復(fù)雜度降低為O（1）。

5、計(jì)算一個(gè)數(shù)值的二進(jìn)制數(shù)中有多少個(gè)1

相信有了之前的基礎(chǔ)，大家很容易實(shí)現(xiàn)這個(gè)算法。單純的通過(guò)位運(yùn)算，與1進(jìn)行與運(yùn)算，看是否結(jié)果為1，然后右移1位，繼續(xù)判斷。Python代碼實(shí)現(xiàn)如下：

def number1Bit(x):
 count = 0
 while x:
 count = count + (x&1)
 x = x >> 1
 return count

這樣存在一個(gè)問(wèn)題，就是如果有連續(xù)多個(gè)0，那么需要做多次移位操作。有沒(méi)有簡(jiǎn)單的方式跳過(guò)連續(xù)多個(gè)0的情況？

那就是通過(guò)與（x-1）進(jìn)行&運(yùn)算。這里可能不太好理解，舉例說(shuō)明一下

x 1110 0000
x - 1 1101 1111
x&(x-1) 1100 0000

通過(guò)這種方式，會(huì)把最后的那個(gè)1檢測(cè)出來(lái)。

Python代碼實(shí)現(xiàn)如下：

def number1Bit(x):
 count = 0
 while x:
 count = count + 1
 x = x & (x-1)
 return count

總結(jié)：

1、與運(yùn)算通常應(yīng)用的場(chǎng)景是獲取某一位的值為1還是0（如判斷奇數(shù)偶數(shù)，統(tǒng)計(jì)數(shù)值中1的個(gè)數(shù)）；

2、左移右移特性：左移一位相當(dāng)于乘以2，右移一位相當(dāng)于除以2；

3、異或特性：任意數(shù)和自身異或結(jié)果為0；0和任意數(shù)異或結(jié)果還是其本身。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論