緒
想起很久以前有個朋友有一天突然 LINE 我說："ㄟㄟ，我終於知道資工跟資管的差距在哪了。"接者丟了一題 Leetcode 給我。題目很簡單，就一句話：
Given a non-empty array of integers, every element appears twice
except for one. Find that single one.
且其有一些額外條件：
Your algorithm should have a linear runtime complexity. Could you
implement it without using extra memory?
接著給我看排名第一名的解答，運用了 XOR 解法，程式碼如下：
public int singleNumber(int[] A) {
int x = 0;
for (int a : A) {
x = x ^ a;
}
return x;
}
世上竟有如此力與美的程式碼，竟然想得到運用 XOR 歸零律的特性來解這道題...不禁捏了把冷汗，腦中瞬間浮出這樣一句話：我的三維世界是二進制的...
但本質上，不過人跟人之間的差距罷了。
最近對岸很紅的前端工程師 - 郭宇，28歲達到財務自由，退休旅居日本經營溫泉旅館。可是人家大學讀的是政治與行政管理...
扯遠了，繼續回來位元運算的話題。
剛好最近欣賞了一下 HashMap 的原始碼，截一段分享一下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到 HashMap Source Code 裡充滿了這種力與美的 Code，又猛然想起多年前那位朋友的那一番話，決定來簡單聊聊位元運算。
淺嚐位元運算
在計算機系統中數據是由二進制表示，二進制中的一位元，是資訊的最小單位。而位元運算，指的是直接對記憶體中的二進制位元進行操作，因此執行效率非常高。適當使用會大大提高程式的性能。
先來看看基本的位元運算操作：
位元OR
位元或運算
Example:
int a = 45;
int b = 25;
int c = a | b;
//a：0000 0000 0000 0000 0000 0000 0010 1101
//b：0000 0000 0000 0000 0000 0000 0001 1001
//c：0000 0000 0000 0000 0000 0000 0011 1101
//c：61
位元AND
位元且運算
Example:
int a = 45;
int b = 25;
int c = a & b;
//a：0000 0000 0000 0000 0000 0000 0010 1101
//b：0000 0000 0000 0000 0000 0000 0001 1001
//c：0000 0000 0000 0000 0000 0000 0000 1001
//c：9
位元XOR
位元互斥或運算
Example:
int a = 45;
int b = 25;
int c = a ^ b;
//a：0000 0000 0000 0000 0000 0000 0010 1101
//b：0000 0000 0000 0000 0000 0000 0001 1001
//c：0000 0000 0000 0000 0000 0000 0011 0100
//c：52
位元補數
位元取反，0變1、1變0
Example:
int a = 45;
a = ~a;
//移位前：0000 0000 0000 0000 0000 0000 0010 1101
//移位後：1111 1111 1111 1111 1111 1111 1101 0010
位移運算
進行位元的位移操作，又區分有號位移與無號位移
有號位移
- " << " 左移運算：向左進行位移運算，高位丟棄，低位補0
int a = 8;
a << 3;
//移位前：0000 0000 0000 0000 0000 0000 0000 1000
//移位後：0000 0000 0000 0000 0000 0000 0100 0000
- " >> " 右移運算：向右進行位移運算，無號數高位補0；有號數高位補符號位
unsigned int a = 8;
a >> 3;
//移位前：0000 0000 0000 0000 0000 0000 0000 1000
//移位後：0000 0000 0000 0000 0000 0000 0000 0001
int a = -8;
a >> 3;
//移位前：1111 1111 1111 1111 1111 1111 1111 1000
//移位後：1111 1111 1111 1111 1111 1111 1111 1111
無號位移
基本同上，差別在右移時不管符號高位直接補0
- 無號右移運算
int a = -16;
a >>> 2;
//移位前：1111 1111 1111 1111 1111 1111 1111 0000
//移位後：0011 1111 1111 1111 1111 1111 1111 1100
奇技淫巧
以上稍微聊過位元運算的基本操作，接下來來看看有哪些其有哪些經(奇)典(技)應(淫)用(巧)吧
2的冪次乘除運算
int a = 5;
a << 3;
//等價於 a * 2 * 2 * 2
a >> 3;
//等價於 a / 2 / 2 / 2
判斷數字的奇偶性
透過判斷數字二進制位元最低位是否為0來得知其奇偶性
public void Test(int a){
if((a & 1) == 0){
System.out.println("a是偶數");
}else{
System.out.println("a是奇數");
}
}
不使用temp交換兩變數值
利用 XOR 自反性： A XOR B XOR B = A XOR 0 = A
public void exchange(int a,int y){
x ^= y;
y ^= x;
x ^= y;
}
不用加減乘除做加法
public int Add(int a,int b){
return b == 0 ? a : Add(a ^ b, (a & b) << 1);
}
- 用 XOR 模擬不進位加法 (a ^ b)，得出不進位相加結果
- (a & b) << 1 計算進位值
- (a & b) 為判斷每位元是否進位
- << 1 取得最終進位結果
- 每回 recursion 將 (a ^ b) 與 (a & b) << 1 作相加，直到進位值為0
小結
這篇文章主要分享了一些位元運算的基本操作與花式操作，希望能對它有個基本的了解，不至於看不懂一些原始碼。適當的使用位元運算可以提升程式的效率，但不應一味的追求簡化而忽視了效率，反而本末倒置。
如果覺得對你有幫助，可以幫我點個讚，也歡迎留言交流~~~~
下次見。
