educoder 二進制數據的位運算_二進制與位運算實用操作匯總（基礎篇）

位運算是最高效而且占用內存最少的算法操作，但也是最難看懂的操作。然而，關于位運算的用法，筆者查了許多資料，似乎都沒有找到詳細而系統的講解資料。筆者對位運算的操作相當感興趣，因此斗膽嘗試對位運算來一個的總結。

本文先從基本概念出發，然后從基本概念推導出基礎應用，然后再到算法題實戰。層層推進，逐步迭代。

本人水平有限，如有勘誤，敬請指正。

說明：本文會以Python的交互環境來做代碼演示。關于本文的約定：非代碼塊中的二進制數以下標x來表示進制數，如十進制數15，用二進制表示為

，而用十六進制則表示為

；

所有代碼塊中的二進制數字都以0b開頭，比如十進制數15，用二進制表示為0b1111；

有時候需要更直觀地表示，會使用豎式表示，如兩個二進制數的and操作表示為：

所有代碼塊中的十六進制數字都以0x開頭，比如十進制數255，用十六進制表示為0xff；

bin()函數，是Python中把十進制轉換為二進制的轉換函數；

所有的位運算操作的命名均用英文命名，以增加辨識度。

概念篇

and 操作，操作符“&”

定義：稱為按位與運算符。它對整型參數的每一個二進制位進行布爾與操作，即兩個對應的二進制位同時為1時，才等于1。

or 操作，操作符“|”

定義：稱為按位或運算符。它對整型參數的每一個二進制位進行布爾或操作，即兩個對應的二進制位，任意一個為1時，就等于1。

xor操作，操作符“^”

定義：稱為按位異或運算符。它對整型參數的每一個二進制位進行布爾異或操作，即兩個對應的二進制位，有且僅有一個為1時，才等于1。

not操作，操作符“~”

定義：稱為按位非運算符。它是一個單運算符，對運算數的所有二進制位進行取反操作。

shl操作，操作符“<

定義：稱為按位左移運算符。它把第一個運算數的所有二進制位向左移動第二個運算數指定的位數，而新的二進制位補0。將一個數向左移動N個二進制位相當于將該數乘以2的N次方，比如：

，

shr操作，操作符“>>”

定義：稱為按位右移運算符。它把第一個運算數的所有二進制位向右移動第二個運算數指定的位數。為了保持運算結果的符號不變，左邊二進制位補 0 或 1 取決于原參數的符號位。如果第一個運算數是正的，運算結果最高位補 0；如果第一個運算數是負的，運算結果最高位補 1。將一個數向右移動N個二進制位相當于將該數除以2的N次方，比如：

，

(總是向負無窮方向取整)。

原理篇

進制轉換

進制之間的轉換其實是個數學問題，在實際應用中，我們基本上無需操心。因此這里想說的不是計算問題，而是邏輯問題。二進制與十六進制有著天然的聯系——每四個二進制位可以代表一個十六進制位：

由上圖可見，如果說二進制轉十進制還要稍稍心算一下的話，那二進制轉十六制可以馬上得出。只要記住了一個十六進制位與四個二進制位的對應關系就好了。同理，八進制位與二進制的關系是，每三個二進制位對應一個八進制位，但實踐中，八進制并不常見，因此點到即止。

那么，為什么二進制與十六進制在實踐中更常見呢？這是與內存的儲存單位有關。

字節與二進制數的關系

對于計算機而言，最小的儲存單位是一個字節，英文為byte。byte既是一個單位，也是一種數據類型(關于數據類型的解釋，可查閱C/C++、JAVA等靜態類語言的相關資料，本文不作介紹)。對于一個byte的數據，用了八個二進制位去儲存數據，因此能正好用兩個十六進制位來省略表示(比十進制還少寫一位)。這就是為什么在實際操作中，二進制與十六進制更常見的原因。

二進制運算符的操作范圍

筆者查閱了許多二進制運算的相關資料，似乎都忽略了對這一點的介紹。二進制運算符的作用范圍與參與運算的變量的數據類型有關，比如以JAVA為例：對于byte類型變量，由于byte以8-bit(8個二進制位)表示，因此相應的位運算符的作用范圍就是8-bit；

對于int類型變量，由于int以32-bit表示，因此位運算符的作用范圍就是32-bit；

假如兩個大小不一的數據類型進行操作，那位運算的作用范圍會以較大的數據類型作為基準范圍。

二進制數的符號

有了數據類型的范圍限定，因此才有了高位、低位、符號位的概念。高位，指在數據類型限定范圍內靠左的二進制位；

低位，指在數據類型限定范圍內靠右的二進制位；

符號位，指在數據類型限定范圍內最左邊的一個二進制位，符號位為0表示正數，1表示負數。(除了C語言存在無符號的值類型外，絕大部分語言的值類型都默認為有符號的數值類型)

因此，假如一個byte范圍內的整數，提升為一個int范圍內的整數，由于二進制位數的范圍大了，必然需要進行補位，因此：當原byte整數為正數時，提升為int類型時，補位全部以0補位；

當原byte整數為負數時，提升為int類型時，補位全部以1補位；

為什么要這樣做？因為這樣才能保證數值在范圍提升后，原值的十進制數不變。以下來看看JAVA的驗證代碼：

// byte類型的值范圍是[-128,127]byte a = (byte) -55; //由于值在byte范圍內，因此強制轉換縮小變量內存范圍不會改變原值byte b = (byte) 100;

System.out.println(Integer.toBinaryString(a)); //輸出(二進制數)：11111111111111111111111111001001System.out.println(Integer.valueOf(a)); //輸出：-55(重新提升范圍，值不變)System.out.println(Integer.toBinaryString(b)); //輸出(二進制數)：1100100(高位的0會被省略顯示)System.out.println(Integer.valueOf(b)); //輸出：100

二進制下的負數表示法

對于一個十進制的負數，我們經常把它看作是一個數加一個負號；然而對于二進制負數來講，卻不是一堆二進制位數加一個符號位。

二進制的正數與負數之間的關系更像是“進位”的關系。以下我們以一個byte值來舉例：

如上所述，byte的數值范圍是[-128,127]。

為了讓表示更清楚，筆者特意把符號位隔開。留意從0到-1，由于非符號位全部為0，已經沒有東西可減，但假如我們假設從更高的位借來了一個1，這樣就能讓

了；有了-1，那

就可以繼續成立了……直到把除符號位之外的位全部減完，這時十進制數就相當于-128。因此，八位二進制數可以表達的數為

個，即[-128,127]。

二進制數的性質

由以上的二進制數變化規律，我們可以發現二進制數有以下性質：～x = -x - 1：從以上0與-1的按位關系可以看到，兩者的二進制位正好取反；此規律能推廣到1與-2，2與-3……等等。因此，該性質是not操作中最常使用的性質。

(~x)&x = 0：任意數與它的取反數的and操作結果為0。

(~x)|x = -1：任意數與它的取反數的or操作結果為-1。