[[339195]]

計算機說到底就是 0 和 1，所有的數(shù)在內存中都是以二進制的形式儲存的。

而位操作，或者說位運算，就是直接對內存中的二進制位進行操作。

位運算可以說是我們的基本功，今天這篇文章就從以下角度和大家一起玩轉位運算。

1. 位運算究竟有什么用?
2. 原碼 反碼 補碼
3. 7 種位運算

當然了，位運算還有很多奇技淫巧，如果大家還想看進階篇，記得給我點贊或者留言告訴我哦～

位運算的作用

在實際生產中，位運算是用來優(yōu)化時間和空間的。

位運算可能并不會降低復雜度的等級，但是可以把復雜度前面的系數(shù)降下來。

舉個例子。

大家都知道堆，或者叫優(yōu)先隊列，一般來說是用完全二叉樹來實現(xiàn)的，叫做二叉堆。

最小堆

 

二叉堆插入、刪除元素的時間復雜度都是 O(logn)，如果這個不清楚的同學趕緊在公眾號內回復「堆」復習一下，或者點擊這里～

但是有另一種堆，它能夠做到 O(1) 的時間插入元素，O(logn) 的時間刪除元素，我在堆這篇文章里也提到過，就是斐波那契堆。

但為什么不用呢?

就是因為 O(1) 前面的系數(shù)非常大。

 

我們說 O(logn) 比 O(1) 好，是有個條件的，那就是 n 非常非常大的情況下，但是實際上，如果 n 是在 int 范圍內，那么取個 log 也不過就是 32 了，反而這個 O(1) 的時間復雜度可能系數(shù)達到幾百幾千。

一般來說實際應用中時間的測量并不是像我們做算法題時用時間復雜度這么簡單，有的時候就需要你把兩個算法都實現(xiàn)出來，去跑去測量它的時間，才能決定哪個好。

那么二進制一次能夠作用于 32 位上(假設是一個 int)，如果數(shù)據(jù)表示的巧妙，這完全可以優(yōu)化 32 倍，多用幾個 int 就多優(yōu)化了好幾個 32 倍，不香嗎?

 

除了優(yōu)化時間，還可以優(yōu)化空間。

比如在網(wǎng)站發(fā)布新版本時，一般都會附上支持該版本的瀏覽器列表，不然有些老掉牙的瀏覽器看不到我的新功能還算我的鍋么?

那么怎么有效的表示這個瀏覽器列表呢?

全世界所有瀏覽器都有個國際標準編號，這里我就簡單假設一下：

• 0 表示 QQ 瀏覽器
• 1 表示 Chrome 瀏覽器
• 2 表示火狐瀏覽器
• 3 表示 ...

那么我們就可以用一個 int 表示是否支持這些瀏覽器的狀態(tài)，如果這個瀏覽器能用，那么這一位上就設為 1，不能用就設為 0，這樣用一個 int 就能表示 32 個網(wǎng)站。

那么國內的某個網(wǎng)站可以表示為：

• 0b .... 1101

所以位操作在很多代碼里都很常用，比如網(wǎng)絡協(xié)議、操作系統(tǒng)等等。

這就是位運算的兩大優(yōu)勢，接下來我們說說具體的知識點。

原碼 反碼 補碼

數(shù)字有正有負，Java 中用的是 signed type，就是有正有負的。

雖然在 Java 8 之后，也用了個工具來實現(xiàn) unsigned type，但是其實底層實現(xiàn)是沒有的。

二進制最左邊的一位是符號位，

• 0 表示這個數(shù)是非負數(shù);
• 1 表示這個數(shù)是負數(shù)。

對了，最左邊的一位英文叫做 most significant bit，別說錯了。。。

正數(shù)

正數(shù)的原碼反碼補碼相同，沒啥好說的。

比如：

• int 1 = 0b 0000 0000 0000 0001
• int 2 = 0b 0000 0000 0000 0010

負數(shù)：

原碼：把相應的正數(shù)的符號位設為 1。

• -1 的原碼 = 0b 1000 0000 0000 0001
• -2 的原碼 = 0b 1000 0000 0000 0010

反碼 ones' complement：

符號位是 1，其余位取反。

• -1 的反碼 = 0b 1111 1111 1111 1110
• -2 的反碼 = 0b 1111 1111 1111 1101

補碼 two's complement ：

反碼 + 1。

• -1 的補碼 = 0b 1111 1111 1111 1111
• -2 的補碼 = 0b 1111 1111 1111 1110

而計算機中真正用來存儲數(shù)據(jù)的是用補碼。

這里稍微注意下反碼和補碼的英文，ones' 的這個 ' 在后面，two's 的這個 ' 在中間。。

為什么計算機要用補碼來存儲數(shù)據(jù)呢?

可能有同學會說正零負零的原因，但這只是表面現(xiàn)象。

實際上通過補碼這樣精巧的設計，計算機做加減乘除運算就不用考慮符號，就可以讓硬件里 CPU 的設計變得異常簡單。

最初計算機只有加法器沒有減法器，所以它用這么一種方式用加法完成了減法。

int 的最大值是多少?

正是因為最左邊一位是符號位，所以正數(shù)的表示就少了一位能用的，那么 int 的最大值就是：

0111111...11 (31 ones) = 2^31 - 1 = 2147483647

7 種位運算

運算符	中文	英文	運算規(guī)則
<<	左移	left shift	右邊補充 0
>>	右移	signed right shift	左邊補充符號位
>>>	無符號右移	unsighed right shift	Java 特有，左邊補充 0
~	位非	NOT	每位取反
&	位與	bitwise AND	每位做與操作，都是 1 則為 1，否則為 0
I	位或	OR	每一位做或操作，有 1 則為 1，否則為 0
^	異或	XOR	相同為 0，不同為 1

要注意的是前 4 個運算符是對 1 個數(shù)進行操作的，且操作完成后這個數(shù)本身的值不變(與 i++ 不同);后 3 個操作是兩個數(shù)的運算。

我們一一來看。

為了書寫方便，下面的數(shù)值雖然是 int 類型，但我只寫 8 位，大家都能理解的噢!

1. <<

左移操作就是把這些零啊壹啊的整體往左移動 n 位，右邊缺的就補充 0。

• 1 = 0b 0000 0001
• 1 << 1 = 0b 0000 0010 = 2
• 2 = 0b 0000 0010
• 2 << 1 = 0b 0000 0100 = 4
• 3 = 0b 0000 0011
• 3 << 1 = 0b 0000 0110 = 6

誒，大家發(fā)現(xiàn)沒有，左移 1 位之后這個數(shù)相當于乘2。

但是這只適用于左邊溢出的高位中不包含 1 時。

如果把 1 扔了，那就肯定不是 2 倍了嘛。

 

2. >>

右移操作就是整體往右移動 n 位，左邊缺的補充符號位。

• 1 = 0b 0000 0001
• 1 >> 1 = 0b 0000 0000 = 0
• 2 = 0b 0000 0010
• 2 >> 1 = 0b 0000 0001 = 1
• 3 = 0b 0000 0011
• 3 >> 1 = 0b 0000 0001 = 1

同理，正數(shù)右移操作的效果是這個數(shù)除以 2。

如果是負數(shù)呢?

• -3 = 1111 1101
• -3 >> 1 = 1111 1110 = -2

因為 Java 是向零取整，所以奇數(shù)時會有問題，就不再是除以 2 的結果。

總結一下，

• 對于非負數(shù)、負數(shù)且是偶數(shù)，右移一位與除以 2 結果一樣;
• 對于負數(shù)且是奇數(shù)，右移一位不等于除以2。

3. >>>

和 >> 的不同之處在于，這個的左邊空缺的不論正負，一律補充 0。

所以對于正數(shù)來說，和 >> 的效果一樣，但是負數(shù)不同。

• -3 = 1111 1101
• -3 >> 1 = 01111 1110 = 很大的數(shù)。。

4. ～

取反操作，就是每一位取反，1變成0，0變成1。

• 3 = 0b 0000 0011
• ~3 = 0b 1111 1100

5. &

這個符號其實和邏輯與運算 && 意思一樣，只不過作用在每一位上。

對于每一位來說，兩個數(shù)都是真，則為真，否則為假。

• 3 = 0b 0000 0011
• 5 = 0b 0000 0101
• 3&5 = 0b 0000 0001

6. |

同理，和邏輯或運算 || 意思一樣，只不過作用在每一位上。

對于每一位來說，但凡有個真的就是真，否則為假。

• 3 = 0b 0000 0011
• 5 = 0b 0000 0101
• 3|5 = 0b 0000 0111

7. ^

最后一個異或操作，相同為 0，不同為 1。

• 3 = 0b 0000 0011
• 5 = 0b 0000 0101
• 3^5 = 0b 0000 0110

 

好啦，以上就是位運算的基本操作了，由這些運算做些巧妙的組合還可以得到很多有趣的結果，大家喜歡的話記得點贊評論哦～

本文轉載自微信公眾號「碼農田小齊」，可以通過以下二維碼關注。轉載本文請聯(lián)系碼農田小齊公眾號。