你不知道的按位運算

luoyibu 發(fā)布于2019-07-24 18:09 / 1184人閱讀

摘要：相信大家都知道二進制數(shù)按位運算的規(guī)則來看一些簡單的例子單純的二進制位之間的這些運算相當(dāng)簡單，但對我們實際編程并沒有直接幫助，因為編程過程中需要的經(jīng)常是數(shù)字間的運算，比如。

先來看LeetCode上的Divide Two Integers題目要求：

Divide two integers without using multiplication, division and mod operator.

就是說不用乘法，除法，求模運算來實現(xiàn)兩個整數(shù)相除，看起來很簡單，我可以用除數(shù)減去被除數(shù)，直到除數(shù)小于被除數(shù)，記錄減法操作的次數(shù)即可。假設(shè)是計算m/n，那么時間復(fù)雜度為O(m/n)。用Python實現(xiàn)后，Time Limit Exceeded。我們考慮有沒有更加優(yōu)化的算法呢？

如果很難想得到，那就先來回憶下二進制數(shù)按位運算的一些知識。

二進制數(shù)按位運算

計算機里面所有數(shù)據(jù)都存儲為0，1串，所有的運算歸根到底都轉(zhuǎn)為二進制數(shù)的運算。相信大家都知道二進制數(shù)按位運算的規(guī)則：

來看一些簡單的例子：

1010 & 1100 = 1000
1010 | 1100 = 1110
1010 ^ 1100 = 0110
1010 << 2   = 101000
1010 >> 2   = 10
~1010       = 0101

單純的二進制位之間的這些運算相當(dāng)簡單，但對我們實際編程并沒有直接幫助，因為編程過程中需要的經(jīng)常是數(shù)字間的運算，比如 5*(2^4) 。真的是這樣嗎？接著往下看！

計算機中數(shù)字的存儲方式

我們都知道計算機中萬物皆為0、1，將萬物變?yōu)?、1的過程叫做編碼，這里我們只討論將數(shù)字編碼為0、1的過程。

計算機中對數(shù)字的表示有三種方式：原碼，反碼，補碼：

原碼表示法在數(shù)值前面增加了一位符號位（即最高位為符號位）：正數(shù)該位為0，負(fù)數(shù)該位為1。比如十進制3如果用8個二進制位來表示就是 00000011， -3就是 10000011。

反碼表示方法：正數(shù)的反碼是其本身；負(fù)數(shù)的反碼是在其原碼的基礎(chǔ)上，符號位不變，其余各個位取反。

補碼表示方法：正數(shù)的補碼是其本身；負(fù)數(shù)的補碼是在其原碼的基礎(chǔ)上，符號位不變，其余各位取反，最后+1。 (即在反碼的基礎(chǔ)上+1)

原碼容易被人腦直接識別并用于計算，但是對于計算機來說并不友好。所以在計算機系統(tǒng)中，數(shù)值一律用補碼來表示、運算和存儲。使用補碼，可以將符號位和數(shù)值域統(tǒng)一處理，將加法和減法統(tǒng)一處理。此外，補碼與原碼相互轉(zhuǎn)換，其運算過程是相同的，不需要額外的硬件電路。詳細(xì)的解釋可以參考原碼, 反碼, 補碼詳解。

數(shù)字的按位運算

計算機中數(shù)字存儲為補碼形式，各個數(shù)之間的運算也是對它們的補碼做運算，而且得到的結(jié)果也是補碼，如下圖：

各種編程語言都提供了對補碼的二進制位直接進行運算的方法。以Python為例：

>>> 0b1010 & 0b1100
8   #1000
>>> 0b1010 | 0b1100
14  #1110
>>> 0b1010 ^ 0b1100
6   #0110
>>> 0b1010 << 2
40  #101000
>>> 0b1010 >> 2
2   #10
>>> ~0b1010
-11 #10000000 00000000 00000000 00001011
>>> type(0b1010)

上面0b開頭的0、1串表示整型數(shù)字，在32位操作系統(tǒng)中，Python中int類型一般占32個二進制位，以最后一個求反運算為例子，1010的補碼為

00000000 00000000 00000000 00001010

求反操作后為：

11111111 11111111 11111111 11110101

即為-11(原碼為：10000000 00000000 00000000 00001011)的補碼。（對一個數(shù)的補碼求補碼即可得到該數(shù)的原碼）

另辟蹊徑的按位運算

那么按位運算在實際編程中可以扮演哪些角色呢？簡單點地，可以用來判斷奇、偶數(shù)：num & 0x1，或者對一個數(shù)變換符號：~num + 1；復(fù)雜點的可以用來交換兩個數(shù)，求絕對值等等。

> 不用額外的變量實現(xiàn)兩個數(shù)字互換。

def swap(num_1, num_2):
    num_1 ^= num_2
    num_2 ^= num_1
    num_1 ^= num_2
    return num_1, num_2

證明很簡單，我們只需要明白異或運算滿足下面規(guī)律：

0^a = a;

a^a = 0;

a^b^c = a^c^b;

巧妙運用異或可以高效解決很多問題，比如 找出數(shù)組中只出現(xiàn)了一次的數(shù)（除了一個數(shù)只出現(xiàn)一次外，其他數(shù)都是出現(xiàn)兩次），以及它的升級版：數(shù)組中只出現(xiàn)1次的兩個數(shù)字(百度面試題)。

> 不用判斷語句來實現(xiàn)求絕對值。

def bit_abs(num):
    negative = num >> 31
    return (num ^ negative) - negative

這里假設(shè)程序運行環(huán)境中操作系統(tǒng)為32位，int型整數(shù)(不考慮整數(shù)溢出)用32位存儲，因此可以用 num>>31 取出符號位，后面的部分留給大伙證明。

Leetcode 題目思路

回到文章開始提到的題目中，我們對除數(shù)減去被除數(shù)的過程稍作改進。假設(shè)求m/n，我們不一次次的 m-n，而是找到n的一個倍數(shù)，使得m-x*n盡可能小，這樣能減少循環(huán)減法的次數(shù)，進而提高效率。我們知道在按位操作中，n << k相當(dāng)于 n * 2^k，因此可以用2^k 來找合適的x。

我們需要這樣的一個數(shù)字k，它使得n 2^k < m < n 2^(k+1)，然后用m - n*2^k，得到新的m"。再找相應(yīng)的k"，做減法，如此循環(huán)即可。代碼放在這里。

原文地址

相關(guān)閱讀
Pyhon wiki: BitwiseOperators
位操作基礎(chǔ)篇之位操作全面總結(jié)