计算机系统（1）（荣誉）作业一

1. 证明：异或运算具有结合律，即：( a ⊕ b ) ⊕ c = a ⊕ ( b ⊕ c ) (a⊕b)⊕c=a⊕(b⊕c)(a⊕b)⊕c=a⊕(b⊕c).

证明如下：

方法：遍历所有情况

①a=0,b=0;c=0此时成立

②a=0,b=0;c=1此时成立

③a=0,b=1;c=0此时成立

④a=0,b=1;c=1此时成立

⑤a=1,b=0;c=0此时成立

⑥a=1,b=0;c=1此时成立

⑦a=1,b=1;c=0此时成立

⑧a=1,b=1;c=1此时成立

 综上所述，所有情况下，都有结合律成立，因此异或运算具有结合律。故得证。

2. 异或运算的快速计算方法。对于函数f ( x 1 , ⋯ , x n ) = x 1 ⊕ x 2 ⊕ ⋯ ⊕ x n f(x_1,⋯,x_n )=x_1⊕x_2⊕⋯⊕x_nf(x

因此，时间复杂度O ( l o g ⁡ n ) O(log⁡n )O(log⁡n)，空间复杂度O ( n ) O(n)O(n)

3. 证明并行加法器中定义的进位状态运算符⊗，具有结合律（可以写程序证明）。

证明如下：

编写C++程序如下（由于C++编译器中不能使用⊗，故采用字符*代替字符⊗）：

结果如下：

综上所述，并行加法器中定义的进位状态运算符⊗，具有结合律。故得证。