在日常的Java開發中，位運算使用的不多，使用的更多的是算數運算（+、-、*、/、%）、關係運算（<、>、<=、>=、==、!=）和邏輯運算（&&、||、!），所以相對來說對位運算不是那麼熟悉，本文將以Java的位運算來詳細介紹下位運算及其應用。 1、 位運算起源 位運算起源於C語言的低級操作，Ja ...
在日常的Java開發中，位運算使用的不多，使用的更多的是算數運算（+、-、*、/、%）、關係運算（<、>、<=、>=、==、!=）和邏輯運算（&&、||、!），所以相對來說對位運算不是那麼熟悉，本文將以Java的位運算來詳細介紹下位運算及其應用。
1、 位運算起源
位運算起源於C語言的低級操作，Java的設計初衷是嵌入到電視機頂盒內，所以這種低級操作方式被保留下來。所謂的低級操作，是因為位運算的操作對象是二進位位，但是這種低級操作對電腦而言是非常簡單直接，友好高效的。在簡單的低成本處理器上，通常位運算比除法快得多，比乘法快幾倍，有時比加法快得多。雖然由於較長的指令流水線和其他架構設計選擇，現代處理器通常執行加法和乘法的速度與位運算一樣快，但由於資源使用減少，位運算通常會使用較少的功率，所以在一些Java底層演算法中，巧妙的使用位運算可以大量減少運行開銷。
2、 位運算詳解
Java位運算細化劃分可以分為按位運算和移位運算，見下表。
|
細化 |
符號 |
描述 |
運算規則 |
|
按位運算 |
& |
與 |
兩位都為1，那麼結果為1 |
|
| |
或 |
有一位為1，那麼結果為1 |
|
|
~ |
非 |
~0 = 1,~1 = 0 |
|
|
^ |
異或 |
兩位不相同，結果為1 |
|
|
移位運算 |
<< |
左移 |
各二進位位全部左移N位，高位丟棄，低位補0 |
|
>> |
右移 |
各二進位位全部右移N位，若值為正，則在高位插入 0，若值為負，則在高位插入 1 |
|
|
>>> |
無符號右移 |
各二進位位全部右移N位，無論正負，都在高位插入0 |
在進行位運算詳解之前，先來普及下電腦中數字的表示方法。對於電腦而言，萬物皆0、1，所有的數字最終都會轉換成0、1的表示，有3種體現形式，分別是：原碼、反碼和補碼。
原碼：原碼表示法在數字前面增加了一位符號位，即最高位為符號位，正數位該位為0，負數位該位為1.比如十進位的5如果用8個二進位位來表示就是00000101，-5就是10000101。
反碼：正數的反碼是其本身，負數的反碼在其原碼的基礎上，符號位不變，其餘各個位取反。5的反碼就是00000101，而-5的則為11111010。
補碼：正數的補碼是其本身，負數的補碼在其原碼的基礎上，符號位不變，其餘各位取反，最後+1。即在反碼的基礎上+1。5的反碼就是00000101，而-5的則為11111011。
瞭解了這幾個概念後，我們現在先記住一個結論，那就是在電腦系統中，數字一律用補碼來表示、運算和存儲，具體的原因可以看這篇文章的討論，這裡不做更多討論，因為不是本文的重點。
2.1 與運算（&）
規則：轉為二進位後，兩位為1，則結果為1，否則結果為0。
舉例：
|
十進位 |
二進位（正數原碼、反碼、補碼一致） |
|
10 |
00000000000000000000000000001010 |
|
&12 |
&00000000000000000000000000001100 |
|
= |
= |
|
8 |
00000000000000000000000000001000 |
|
十進位 |
二進位（原碼） |
|
-6 |
10000000000000000000000000000110 |
|
&-2 |
&10000000000000000000000000000010 |
|
十進位 |
二進位（反碼） |
|
-6 |
11111111111111111111111111111001 |
|
&-2 |
&11111111111111111111111111111101 |
|
十進位 |
二進位（補碼） |
|
-6 |
11111111111111111111111111111010 |
|
&-2 |
&11111111111111111111111111111110 |
|
= |
= |
|
-6 |
11111111111111111111111111111010 |
最後的計算結果11111111111111111111111111111010還是補碼的形式，要看其十進位，還需要先轉成二進位原碼。
先轉反碼：11111111111111111111111111111010-1=11111111111111111111111111111001，得反碼11111111111111111111111111111001。
再轉原碼：在反碼的基礎上轉原碼，符號位不變，其他各位取反，得10000000000000000000000000000110。第一位1代表負數，後面0110轉成十進位是6，得-6。
2.2 或運算（|）
規則：轉為二進位後，有一位為1，則結果為1，否則結果為0。
舉例：
|
十進位 |
二進位（正數原碼、反碼、補碼一致） |
|
10 |
00000000000000000000000000001010 |
|
|12 |
|00000000000000000000000000001100 |
|
= |
= |
|
14 |
00000000000000000000000000001110 |
|
十進位 |
二進位（原碼） |
|
-6 |
10000000000000000000000000000110 |
|
|-2 |
|10000000000000000000000000000010 |
|
十進位 |
二進位（反碼） |
|
-6 |
11111111111111111111111111111001 |
|
|-2 |
|11111111111111111111111111111101 |
|
十進位 |
二進位（補碼） |
|
-6 |
11111111111111111111111111111010 |
|
|-2 |
|11111111111111111111111111111110 |
|
= |
= |
|
-2 |
11111111111111111111111111111110 |
2.3 非運算（~）
規則：轉為二進位後，~0 = 1,~1 = 0。
舉例：
|
十進位 |
二進位（正數原碼、反碼、補碼一致） |
|
~7 |
~00000000000000000000000000000111 |
|
= |
= |
|
-8 |
11111111111111111111111111111000（補碼需轉換為原碼） |
11111111111111111111111111111000-1得反碼，可以把1000看成是0112，得反碼11111111111111111111111111110111。根據反碼得原碼10000000000000000000000000001000。
|
十進位 |
二進位（原碼） |
|
~（-6） |
~10000000000000000000000000000110 |
|
十進位 |
二進位（反碼） |
|
~（-6） |
~11111111111111111111111111111001 |
|
十進位 |
二進位（補碼） |
|
~（-6） |
~11111111111111111111111111111010 |
|
= |
= |
|
5 |
00000000000000000000000000000101（正數原碼、反碼、補碼一致） |
2.4 異或運算（^）
規則：轉為二進位後，兩位不相同，結果為1，否則為0。
舉例：
|
十進位 |
二進位（正數原碼、反碼、補碼一致） |
|
15^2 |
00000000000000000000000000001111 ^00000000000000000000000000000010 |
|
= |
= |
|
13 |
00000000000000000000000000001101 |
2.5 左移運算（<<）
規則：轉為二進位後，各二進位位全部左移N位，高位丟棄，低位補0。
舉例：
|
十進位 |
二進位（正數原碼、反碼、補碼一致） |
|
2<<2 |
00000000000000000000000000000010 |
|
= |
0000000000000000000000000000001000 |
|
8 |
00000000000000000000000000001000 |
|
十進位 |
二進位（先取補碼 再對補碼操作位移） |
|
-2<<2 |
10000000000000000000000000000010（原碼） |
|
|
11111111111111111111111111111101（反碼） |
|
|
11111111111111111111111111111110（補碼） |
|
|
1111111111111111111111111111111000 |
|
|
11111111111111111111111111111000（補碼） |
|
|
11111111111111111111111111110111（反碼） |
|
-8 |
10000000000000000000000000001000（原碼） |
2.6 右移運算（>>）
規則：轉為二進位後，各二進位位全部右移N位，若值為正，則在高位插入 0，若值為負，則在高位插入 1。
舉例：
|
十進位 |
二進位（正數原碼、反碼、補碼一致） |
|
2>>2 |
00000000000000000000000000000010 |
|
= |
0000000000000000000000000000000010 |
|
0 |
00000000000000000000000000000000 |
|
十進位 |
二進位（先取補碼 再對補碼操作位移） |
|
-6>>2 |
10000000000000000000000000000110（原碼） |
|
|
11111111111111111111111111111001（反碼） |
|
|
11111111111111111111111111111010（補碼） |
|
|
1111111111111111111111111111111010 |
|
|
11111111111111111111111111111110（補碼） |
|
|
11111111111111111111111111111101（反碼） |
|
-2 |
10000000000000000000000000000010（原碼） |
2.7 無符號右移運算（>>>）
規則：轉為二進位後，各二進位位全部右移N位，無論正負，都在高位插入0。
舉例：
|
十進位 |
二進位（先取補碼 再對補碼操作位移） |
|
-1>>>1 |
10000000000000000000000000000001（原碼） |
|
|
11111111111111111111111111111110（反碼） |
|
|
11111111111111111111111111111111（補碼） |
|
|
011111111111111111111111111111111 |
|
|
01111111111111111111111111111111（補碼） |
|
|
01111111111111111111111111111110（反碼） |
|
溢出，只能表示到int的最大值2147483647 |
10000000000000000000000000000001（原碼） |
3、 應用
3.1 不用額外的變數實現兩個數字互換
見參考資料中的BitOperationTest，方法reverse通過三次異或操作完成了兩個變數值的替換。
證明很簡單，我們只需要明白異或運算滿足下麵規律（實際不止如下規律）：
0^a = a，a^a = 0；
a ^ b = b ^ a；
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c；
a ^ b ^ a = b；
假設a,b兩個變數，經過如下步驟完成值交換：a=a^b,b=b^a,a=a^b。
證明如下：
因為a ^ b = b ^ a，又a=a^b,b=b^a。故b=b^a= b^ (a^b)=a。
繼續a=a^b，a=（a^b) ^ b^ (a^b)，故a=b。完成值交換。
3.2 不用判斷語句實現求絕對值
公式如下：(a^(a>>31))-(a>>31)
先整理一下使用位運算取絕對值的思路：若a為正數，則不變，需要用異或0保持的特點；若a為負數，則其補碼為原碼翻轉每一位後+1，先求其原碼，補碼-1後再翻轉每一位，此時需要使用異或1具有翻轉的特點。
任何正數右移31後只剩符號位0，最終結果為0，任何負數右移31後也只剩符號位1，溢出的31位截斷，空出的31位補符號位1，最終結果為-1.右移31操作可以取得任何整數的符號位。
那麼綜合上面的步驟，可得到公式。a>>31取得a的符號，若a為正數，a>>31等於0，a^0=a，不變；若a為負數,a>>31等於-1 ，a^-1翻轉每一位。
3.3 判斷一個數的奇偶性
通過與運算判斷奇偶數，偽代碼如下：
n&1 == 1?”奇數”:”偶數”
奇數最低位肯定是1，而1的二進位最低位也是1，其他位都是0，所以所有奇數和1與運算結果肯定是1。
參考資料:
https://github.com/lingjiango/ConcurrentProgramPractice
https://en.wikipedia.org/wiki/Bitwise_operation
https://www.zhihu.com/question/20159860
