位元計算

C 語言提供以下 6 種位元計算符號，它們可以作用在 char、short、int 或 long 這些基本型態的變數或常數上。

&	位元 AND 計算，例如 (0xA3 & 0x36) 得到 0x22，因為 1010 0011 AND 0011 0110 -------------- 0010 0010
|	位元 OR 計算，例如 (0xA3 | 0x36) 得到 0xB7，因為 1010 0011 OR 0011 0110 -------------- 1011 0111
^	位元 XOR 計算，例如 (0xA3 ^ 0x36) 得到 0x95，因為 1010 0011 XOR 0011 0110 -------------- 1001 0101
~	這是一個單元運算符號 (unary operator)。做位元 NOT 計算。 例如 (~0xA3) 得到 0x5C，因為 NOT 1010 0011 -------------- 0101 1100
<<	位元左移。a << b 之中， b 必須是個非負整數， 代表將 a 的位元組向左移 b 位。 a 的最右邊 b 個位元組補 0， 超過 a 的資料型態含量的部份就消失了。 換句話說，移進來的都是 0，移出去的就不見了。 如果移出去的恰好都是 0，而且資料型態是 unsigned， 則 a<<b 的效果就等於 a*2b。以 0xA3 << 2 為例，產生的位元組是 (10 1000 1100)， 若資料型態的含量超過 11 bits，則會被解讀為 652 (512+128+8+4)。 若資料型態是 unsigned char，則會被解讀為 140 (128+8+4)， 若資料型態是 char，則會被解讀為 -116 (其二補數為 (0111 0100))。
>>	位元右移。a >> b 之中， b 必須是個非負整數， 代表將 a 的位元組向右移 b 位。 移出去的位元就不見了，但是移進來的位元未必是 0。 如果資料型態是 unsigned，或者 a 的最高位恰好是 0， 則移進來的位元必定是 0。 如果不是 unsigned，而且 a 的最高位恰好是 1， 亦即 a 代表負數，則有些編譯器會移進來 0 (稱為邏輯平移 logical shift)， 但有些編譯器會移進來 1 (稱為算術平移 arithmetic shift)。 對不同的編譯器，最好做實驗以求瞭解。

以下這個簡單的程式，將會輸出

2³¹ = 2147483648
2³²-1 = 4294967295
-2³¹ = -2147483648
-1

#include <stdio.h>

main() {
    unsigned int a, b;
    int x, y;
    a = (1 << 31);
    x = (1 << 31);
    b = (~0);
    y = (~0);
    printf("%u\n%u\n%d\n%d\n", a, b, x, y);
}

位元 NOT 計算，經常被用來產生含有許多個 1 的位元組。 位元 AND, OR, XOR 計算，經常被用來讀取或設定資料中特定位元的值。 以下是一些例子。 為了方便起見 (而且大部分的應用的確只需如此)， 以下我們提及的變數名，假設都是 unsigned int 型態。 而且令最右邊的位元是 0 號位元，依序向左是 1 號、2 號、等等。 所以最左邊是 31 號位元，它也就是最高位 (MSB)。

y = (x >> 3) & 1;	y 獲得 x 之 3 號位元的值 (0 或 1)。 其實那對括號是不必要的，但是放在那裡提高可讀性。
x = x | (1 << 3);	將 x 的 3 號位元設定成 1，其他位元都保持不變。 這個語句可以簡寫成 x |= 1 << 3。 此外，還有 &= ^= <<= >>= 這些計算符號，它們的意義都和 += 類似，亦即 x &= p; 等同於 x = (x) & (p);
x &= (1 << 3);	將 x 的 3 號位元保留不變，其他位元全部設定成 0。
x &= ~(1 << 31);	將 x 的最高位設定成 0，其他位元均不改變。
x ^= 1 << 3;	如果 x 的 3 號位元原來是 0，將它設定成 1； 否則設定成 1。這就是 toggle 的意思。
y = x & 0x7F;	y 是 x 最右邊 7 位元的值 (介於 0 和 127 之間)。
y = x >> 25;	y 是 x 最左邊 7 位元的值。
y = (x >> 16) & 0xF	y 是 x 的 19, 18, 17, 16 四個位元的值。
y = (x >> (p-n+1)) & ~(~0 << n)	y 是 x 的 p, p-1, p-2, ..., p-n+1 位元值。 也就是從 p 號開始 (含)，向下連續 n 個位元的值。 觀察 ~(~0 << n) 的位元組就是最右邊連續 n 個 1， 其他位元都是 0。

最後，我們示範一個函式 bcount()， 它計算一個 unsigned int 型態變數的位元組中，共有幾個 1。

int bcount(unsigned int n) {
    int i=0;
    for ( ; n != 0; n >>= 1)
        if (n & 1)
            ++i;
    return i;
}

1. 假設 x 是 unsigned int 型態的變數。 寫一個指令，將 x 的 3 號位元設定成 0，其他位元都保持不變。
2. 假設 x 是 unsigned int 型態的變數。 寫一個指令，使得 x 的 3 號位元保留不變，其他位元全部設定成 1。
3. 寫一個符合以下規格的函式

   unsigned int rotate(unsigned int, int);
   

   使得若 n 是正整數， rotate(x, n) 的回應值是 x 被向右迴旋 (rotate) n 個位元。也就是說，將 x 最右邊的 n 個位元，依序搬移到最左邊。 以 unsigned char 資料為例，11010100 向右迴旋 3 位就是 10011010。 如果 n 是負整數，就向左迴旋 |n| 位。 注意，這個程式應該以週期性函數的方式處理任意大小的整數 n。
4. 寫一個符合以下規格的函式

   int bcount_(unsigned int);
   

   計算輸入的位元組共有幾個 0。
5. 若 n 是 int 型態的變數，此型態以二補數記錄負數。證明

   n &= n-1;
   

   指令具有以下性質： 如果 n 原本不是 0， 則使得 n 的位元組中最靠右的那個 1 變成 0， 其他的位元不變。而如果 n 原本就是 0， 則結果還是 0。
6. 利用 n &= n-1 這個語句的性質， 寫一個符合以下規格的函式

   int bcount(int)
   

   它計算一個 int 型態變數的位元組中，共有幾個 1。

[ 前一節 ]‧[ 後一節 ]‧[ 回目錄 ]

注意：此處所有文件均為原著，個別的版權宣告日後會一一公布， 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片，以免觸犯著作權法。

Created: May 14, 2000
Last Revised: May 16, 2000
© Copyright 2000 Wei-Chang Shann 單維彰

• Back to the home page of Wei-Chang Shann.
• Connect to the home page of Department of Mathematics, National Central University, Taiwan.