位運算的學習、進位轉換和位運算的簡單應用

在了解什麼是 位運算 之前，讓我們先來了解什麼是 位 ？ 位 指計算機存儲信息的最小單位，在二進位數系統中， 位 是通過0或1來表示。在學習一門程式語言的數據類型時，總會告訴我們 int 的存儲需要 4個 位元組 ，取值範圍為 -2 147 483 648 ~ 2 147 483 647 。其實 取值範圍 就是通過 位 計算出來的，由於 1 位元組 = 8 位 ，所以 int 中的 1 用二進位表示為 0000 0000 0000 0000 0000 0000 0000 0001 。所以 位運算 就是直接對整數在內存中的二進位位進行操作。

為了方便，下面學習中以 int 的 2個位元組 演示

十進位轉換為二進位

正整數轉換為二進位

正整數轉換為二進位通常使用 除二倒取余 的方法。下面演示通過此方法求 10 、13 、42 的二進位。

如圖，讓整數不斷的除二，結果餘數寫在右側，當商為 0 時，停止。所以10 的二進位為： 0000 0000 0000 1010 ，13 的二進位為 0000 0000 0000 1101 , 42 的二進位為 0000 0000 0010 1010 。 除了使用 除二倒取余

的方法，也可以把二進位位 對應的 十進位表列出來，在進行進位轉換時，只需要把十進位數拆成 表中對應十進位的和就可以。如：

1111111111111111327681638481924096204810245122561286432168421

如：10的二進位：10 = 8 + 2 為：1010 42的二進位：42 = 32 + 8 + 2 為：101010 13 的二進位：13 = 8 + 4 + 1 為：1101

負整數轉換為二進位

在對負整數求二進位時，需要先將負整數對應的正整數轉換成二進位，接著對二進位取反，然後對結果再加一。如求 -10 的二進位：

-10 的二進位
先求 10 的二進位
0000 0000 0000 1010
取反：
1111 1111 1111 0101
加 1：
1111 1111 1111 0110

所以 -10 的二進位為 1111 1111 1111 0110 。 注意： 在二進位中的最高位為 符號位 ，0 表示為正數，1表示為負數，所以 int 的最大整數的二進位為 0111 1111 1111 1111 1111 1111 1111 1111 ，取值範圍為:

位運算

位運算可以對整型數值的各個位進行操作。位運算符包括下面這幾個：

& ： 按位與 運算符

當兩個整數值 對應位 上都是 1 時，該位返回 1 ,否則返回 0 （同 1 為 1 ）。如：

10 & 13
10 : 0000 0000 0000 1010
13 : 0000 0000 0000 1101
------------------------------------------
結果:0000 0000 0000 1000

| ： 按位或 運算符

當兩個整數值 對應位 上都是 0 時，該位返回 0 ,否則返回 1 (同 0 為 0 )。如：

42 | 13
42 : 0000 0000 0010 1010
13 : 0000 0000 0000 1101
------------------------------------------
結果:0000 0000 0010 1111

^ ： 按位異或 運算符

當兩個整數值 對應位 上的數不相同時，該位返回 1 ,否則返回 0 (不同返回 1 )。如：

42 ^ 13
42 : 0000 0000 0010 1010
13 : 0000 0000 0000 1101
------------------------------------------
結果:0000 0000 0010 0111

~ ： 按位取反 運算符

把整數值 對應位 上的數取反，1 變 0， 0 變 1。

42 : 0000 0000 0010 1010
------------------------------------------
~42: 1111 1111 1101 0101

<< ： 左移 運算符

X << y 把整數 X 的二進位位，向左移動 y 位。末尾 補 0 。相當於 X * 。

13 << 2
13 : 0000 0000 0000 1101
----------------------------------------
<<2: 0000 0000 0011 0100
13 << 2 的結果為：52 -----> 13 * (2^2) = 52

>> ： 右移 運算符

X >> y 把整數 X 的二進位位，向右移動 y 位。開始處補符號位。相當於 X / 取整數。

13 >> 2
13 : 0000 0000 0000 1101
----------------------------------------
>>2: 0000 0000 0000 0011
13 >> 2 的結果為：3 -----> 13 / (2^2) = 3 

-10 >> 2
-10 : 1111 1111 1111 0110
----------------------------------------
>>2 : 1111 1111 1111 1101
-10 >> 2 的結果為：-3 -----> -10 / (2^2) = -3 

簡單應用

判斷奇偶

由於奇數的二進位末尾始終是 1 ,因此我們可以通過 x & 1 判斷末尾是否有 1 來決定是否是奇數。

// 通過： a&1 的方式取二進位的最後一位。
#include
int main(){
\tint a = -3;
\tif(a & 1){
\t\tprintf("奇數：%d\\n",a);
\t}else{
\t\tprintf("偶數：%d\\n",a);
\t}
\treturn 0;
} 

交換

在交換中， ^ 運算符的運算結果可以理解成 記錄兩個數的不同 。好比，我告訴你在一個箱子裡有兩個不一樣顏色的球（紅，藍）。當用手在裡面拿出一個藍球時，裡面剩下的球不用看，顏色肯定是紅色的。

#include
int main(){
\tint a = 3;
\tint b = 2;
\tprintf("a = %d, b = %d\\n",a,b);
\ta = a^b;//告訴 a 和 b 的不同的地方，賦值給 a。
\tb = a^b;// b 通過不同記錄 a,就可以找到原數a，賦值給 b
\ta = a^b;// 此時b的值是原數a,a 通過不同記錄 a,就可以找到原數b，賦值給 a
\tprintf("a = %d, b = %d\\n",a,b);
\treturn 0;
} 

求兩個數的平均數

通過 (x & y) + ((x ^ y) >> 1) 的方式求兩個數的平均數。我的理解是：先通過 (x & y) 取兩個數的公共部分，然後通過 ( x ^ y) 把剩餘部分相加求和通過 >> 1 除以2。以十進位數為例：(12 + 8) / 2 ；12 = 8 + 4, 8 = 8 + 0；所以公共部分是8，剩餘部分是(4 + 0)/2 = 2 ，平均數為 8 + 2 = 10；

#include
int avarge(int x, int y){
\treturn (x & y) + ((x ^ y) >> 1);
}
int main(){
\tint a = 6;
\tint b = 2;
\tprintf("a = %d, b = %d,平均數：%d\\n",a,b,avarge(a,b));
\treturn 0;
} 

判斷一個數是否是2 的冪次

在二進位中， 2 的冪次 的整數是只含有一個 1 ，如 : 0100 , : 1000 。所以，當我們去掉最後一位的 1 時，結果就變成 0 了。通過 x & (x - 1) 來去除最後一位的 1 。

#include
int main(){
\tint a = 7;
\tif (a & (a-1)){
\t\tprintf("a = %d 不是 2 的冪次\\n",a);
\t} else{
\t\tprintf("a = %d 是 2 的冪次\\n",a);
\t}
\treturn 0;
}