Java基礎 -- 位運算
簡(jiǎn)介
程序中的所有數在計算機內存中都是以二進(jìn)制的形式存儲的。位運算(Bitwise operation)就是直接對整數在內存中的二進(jìn)制位進(jìn)行操作，因此其執行效率非常高。
詳解
Java位運算細化劃分可以分為按位運算和移位運算，見(jiàn)下表。
| 符號 | 描述 | 運算規則 | 分類(lèi) |
|---|---|---|---|
| & | 與 | 兩位都為1，那么結果為1 | 按位運算 |
| | | 或 | 有一位為1，那么結果為1 | 按位運算 |
| ~ | 非 | ~0 = 1,~1 = 0 | 按位運算 |
| ^ | 亦或 | 兩位不相同，結果為1 | 按位運算 |
| << | 左移 | 各二進(jìn)制位全部左移N位，高位丟棄，低位補0 | 移位運算 |
| >> | 右移 | 各二進(jìn)制位全部右移N位，若值為正，則在高位插入 0，若值為負，則在高位插入 1 | 移位運算 |
| >>> | 無(wú)符號右移 | 各二進(jìn)制位全部右移N位，無(wú)論正負，都在高位插入0 | 移位運算 |
在進(jìn)行位運算詳解之前，先來(lái)普及下計算機中數字的表示方法。對于計算機而言，萬(wàn)物皆0、1，所有的數字最終都會(huì )轉換成0、1的表示，有3種體現形式，分別是：原碼、反碼和補碼。
- 原碼：原碼表示法在數字前面增加了一位符號位，即最高位為符號位，正數位該位為0，負數位該位為1.比如十進(jìn)制的5如果用8個(gè)二進(jìn)制位來(lái)表示就是00000101，-5就是10000101。
- 反碼：正數的反碼是其本身，負數的反碼在其原碼的基礎上，符號位不變，其余各個(gè)位取反。5的反碼就是00000101，而-5的則為11111010。
- 補碼：正數的補碼是其本身，負數的補碼在其原碼的基礎上，符號位不變，其余各位取反，最后+1。即在反碼的基礎上+1。5的反碼就是00000101，而-5的則為11111011。
了解了這幾個(gè)概念后，我們現在先記住一個(gè)結論，那就是在計算機系統中，數字一律用補碼來(lái)表示、運算和存儲，具體的原因可以看這篇文章的討論，這里不做更多討論，因為不是本文的重點(diǎn)。
與運算（&）
規則：轉為二進(jìn)制后，兩位為1，則結果為1，否則結果為0。
或運算（|）
規則：轉為二進(jìn)制后，有一位為1，則結果為1，否則結果為0。
非運算（~）
規則：轉為二進(jìn)制后，~0 = 1,~1 = 0。
異或運算（^）
規則：轉為二進(jìn)制后，兩位不相同，結果為1，否則為0。
左移運算（<<）
規則：轉為二進(jìn)制后，各二進(jìn)制位全部左移N位，高位丟棄，低位補0。
右移運算（>>）
規則：轉為二進(jìn)制后，各二進(jìn)制位全部右移N位，若值為正，則在高位插入 0，若值為負，則在高位插入 1。
無(wú)符號右移運算（>>>）
規則：轉為二進(jìn)制后，各二進(jìn)制位全部右移N位，無(wú)論正負，都在高位插入0。
應用
不用額外的變量實(shí)現兩個(gè)數字互換
見(jiàn)參考資料中的BitOperationTest，方法reverse通過(guò)三次異或操作完成了兩個(gè)變量值的替換。
證明很簡(jiǎn)單，我們只需要明白異或運算滿(mǎn)足下面規律（實(shí)際不止如下規律）：
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兩個(gè)變量，經(jīng)過(guò)如下步驟完成值交換：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。完成值交換。
不用判斷語(yǔ)句實(shí)現求絕對值
公式如下：(a^(a>>31))-(a>>31)
先整理一下使用位運算取絕對值的思路：若a為正數，則不變，需要用異或0保持的特點(diǎn)；若a為負數，則其補碼為原碼翻轉每一位后+1，先求其原碼，補碼-1后再翻轉每一位，此時(shí)需要使用異或1具有翻轉的特點(diǎn)。
任何正數右移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翻轉每一位。
判斷一個(gè)數的奇偶性
通過(guò)與運算判斷奇偶數，偽代碼如下：
n&1 == 1?”奇數”:”偶數”
奇數最低位肯定是1，而1的二進(jìn)制最低位也是1，其他位都是0，所以所有奇數和1與運算結果肯定是1。
查找落單的數
將數組的數全部做異或，最后得到的數就是要找的數，因為和一個(gè)數做兩次異或不會(huì )改變。
參考文章: 一文搞懂位運算
評論
