歡迎光臨
每天分享高質量文章

這些位運算的妙用,絕對讓你大開眼界

(點擊上方公眾號,可快速關註一起學Python)

 

位運算的性能大家想必是清楚的,效率絕對高。相信愛好原始碼的同學,在學習閱讀原始碼的過程中會發現不少原始碼使用了位運算。但是為啥在實際編程過程中應用少呢?想必最大的原因,是較為難懂。不過,在面試的過程中,在手寫代碼過程中,寫出一兩個位運算的代碼,還會讓面試官眼前一亮的。

 

位運算常用的運算子包括&(按位與), | (按位或),~(按位非),^(按位異或),<< (有符號左移位) >>(有符號右移位)。

 

下麵用幾個例子說明其應用,希望對你有所啟發。

 

1、判斷奇數還是偶數

 

通常判斷奇數還是偶數我們想到的辦法就是除以2,看餘數是否為0。

Python代碼如下:

 

def isodd(x):
    return True if (x % 2 <> 0) else False

 

如何使用位運算呢?

 

我們只需要使用&運算,與1進行&,如果為1,那麼該數為奇數;如果為0,那麼該數是偶數,Python代碼如下:

 

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

2、左移一位相當於乘以2,右移一位相當於除以2

 

在面試的過程中,通常會遇到的一個問題是寫二分查找代碼。

二分查找的代碼如下:

 

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

 

其中有一步是需要取最小小標和最大下標的中間值,若使用位運算子,midpoint = (low + high) >> 1,面試官肯定會對你刮目相看。

 

3、交換兩個數值

 

數值交換的代碼相信大家都非常熟悉了,因為似乎是從學編程語言的最開始就一直用:

 

temp = b
b = a
a = temp

 

但是怎麼使用位運算來完成此功能呢?

 

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

 

確實比較難理解,原理是什麼呢?

第一行,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,完成了數值交換。

 

這裡,總結下異或運算的特性:任意數和自身異或結果為0;0和任意數異或結果還是其本身。 

 

4、尋找資料串列中的獨一無二

 

有一個資料串列(2N+1個整數),只有一個數出現了1次,其餘N個數都出現了2次。如何找到這個獨一無二的資料?

 

看到這個題目,相信大家第一次想到的演算法肯定是計數,建立串列,迴圈整個資料並計數,然後遍歷這個串列找到出現次數為1的資料。

這樣,空間複雜度為O(N)。

 

如何降低空間複雜度呢?

 

註意看一下剛剛講過的異或的特性:任意數和自身異或結果為0;0和任意數異或結果還是其本身。 

那麼,出現了2次的N個數異或的結果是0,再與出現次數為1次的數異或的結果即為該數。即:找到這個獨一無二資料的辦法是通過對全部的資料進行異或操作,空間複雜度降低為O(1)。

 

5、計算一個數值的二進制數中有多少個1

 

相信有了之前的基礎,大家很容易實現這個演算法。單純的通過位運算,與1進行與運算,看是否結果為1,然後右移1位,繼續判斷。Python代碼實現如下:

 

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

 

這樣存在一個問題,就是如果有連續多個0,那麼需要做多次移位操作。有沒有簡單的方式跳過連續多個0的情況?

 

那就是通過與(x-1)進行&運算。這裡可能不太好理解,舉例說明一下

x           1110 0000

x – 1      1101 1111

x&(x-1) 1100 0000

通過這種方式,會把最後的那個1檢測出來。

 

Python代碼實現如下:

 

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

 

總結:

 

1、與運算通常應用的場景是獲取某一位的值為1還是0(如判斷奇數偶數,統計數值中1的個數);

2、左移右移特性:左移一位相當於乘以2,右移一位相當於除以2;

3、異或特性:任意數和自身異或結果為0;0和任意數異或結果還是其本身。

    赞(0)

    分享創造快樂