CSAPP 2.13 習題解析：用 bis/bic 指令實現位或與異或運算

CSAPP 2.13 習題解析

題目背景：VAX 計算機缺少 AND/OR 指令，僅提供兩條位操作指令：

• bis(x, m)（Bit Set）：將 x 中掩碼 m 為 1 的位設置為 1。等價於 x | m。
• bic(x, m)（Bit Clear）：將 x 中掩碼 m 為 1 的位清零。等價於 x & ~m。

目標

僅使用 bis 和 bic 實現 C 語言的按位 或（|） 和 異或（^） 運算。

解題思路

1. 實現 bool_or (x | y)

直接觀察：bis(x, y) 即為將 x 中 y 為 1 的位置 1，結果恰為 x | y。

int bool_or(int x, int y) {
    return bis(x, y);
}

2. 實現 bool_xor (x ^ y)

異或運算性質：x ^ y = (x & ~y) | (~x & y)。即「x 有而 y 無」或「y 有而 x 無」。

• bic(x, y) = x & ~y（保留 x 中 y 為 0 的位）。
• bic(y, x) = y & ~x（保留 y 中 x 為 0 的位）。
• 將兩者合併：bis(bic(x, y), bic(y, x))。

int bool_xor(int x, int y) {
    return bis(bic(x, y), bic(y, x));
}

驗證邏輯

對每一位分析：

結果完全吻合。這道題展示了如何從原子操作構建複雜邏輯，是理解指令集架構與布爾代數關係的經典案例。