目的: 檢驗學員對 bitwise operator 的認知
1
考慮以下程式碼:
int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3 OP4 y); }
int main() {
int x = 3, y = 5;
return my_xor(x, y);
}
my_xor
嘗試不用 XOR 運算子做出等效的 XOR 運算,其中 OP1, OP2, OP3, OP4 都是 operator,請補完實作。
作答區
OP1 = ?
(a)
|(b)
&(c)
~(d)
%(e)
*OP2 = ?
(a)
|(b)
&(c)
~(d)
%(e)
*OP3 = ?
(a)
|(b)
&(c)
~(d)
%(e)
*OP4 = ?
(a)
|(b)
&(c)
~(d)
%(e)
*2
parity (check) bit 可翻譯為「奇偶校驗位元」或「同位檢查位元」,常見於降低資料傳輸的錯誤。在資料傳送出去前,先在資料原有位元額外加上一個 parity bit,再將 parity bit 與資料的位元所組成的位元傳送出去,待接收完畢後,就檢查看看是否有奇數個 1
或偶數個 1
,以判斷有無發生錯誤。
parity bit 有兩種類型:
1
的個數加起來須為偶數個1
的個數加起來須為奇數個範例 1:
11111110
,其中共有 7 個 1
,奇數個範例 2:
同位元檢查已經廣泛地應用到電腦的主記憶體,其優點是只要利用 XOR 或 NOT,就能製造成硬體;缺點則是無法更正錯誤,也無法偵測到所有錯誤,一旦接收到的位元圖樣同時有偶數個 (2, 4, 6, …個) 位元錯誤,就偵測不到錯誤,因為在這種情況下,1
的個數仍舊會維持奇數個或偶數個。
考慮到以下判斷 parity bit 的程式碼
#include <stdio.h>
/* Generate look-up table while pre-processing */
#define P2(n) n, n ^ 1, n ^ 1, n
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)
/* LOOK_UP is the macro expansion to generate table */
unsigned int table[256] = { LOOK_UP };
int parity(int num) {
/* Number is considered to be of 32 bits */
int max = 16;
// Dividing the number into 8-bit
// chunks while performing XOR
while (max >= 8) {
num = num ^ (num >> max);
max /= N;
}
// Masking the number with 0xff (11111111)
// to produce valid 8-bit result
return table[num & 0xff];
}
int main() {
unsigned int num = 1742346774;
/* Result is 1 for odd parity, 0 for even parity */
int result = parity(num);
printf("%s parity\n", parity(num) ? "odd" : "even");
return 0;
}
補完程式碼。
作答區
N = ?
(a)
8(b)
7(c)
6(d)
5(e)
4(f)
3(g)
2(h)
1延伸題目: 解釋和實作循環冗餘碼 (CRC) 程式碼