今天我会带你把《模块一：计算机组成原理》中涉及的课后练习题，逐一讲解，并给出每个课时练习题的解题思路和答案。

练习题详解

01 | 计算机是什么：“如何把程序写好”这个问题是可计算的吗？

【问题】 可不可以构造一段程序证明停机问题无解?如果可以，请用自己熟悉的语言写出这段程序。

【解析】拿到这道题，我们可以先从问题的抽象入手。

• 判断一段程序是否会停机的方法可以抽象成一个函数。
• 一段程序，也可以抽象成一个函数。

因此，问题可以转换为：存不存在一个通用函数判断另一个函数是否会停止？

接下来，再来构造冲突。

假设存在一个函数 willStop，它只有一个参数 func，willStop 可以判断任意函数 func 是否会停止：

• 如果会停止，返回 true；
• 如果不会停止返回 false。

willStop 具体如何实现我们无法给出，这里只是做一个假设。

func willStop(func){

   //...

}

下面我们构造一组冲突，构造一个叫作wrappedWillStop函数，它调用willStop构造冲突。

function wrappedWillStop(){

  if( willStop(wrappedWillStop) ) {

    while(true){}

  } else {

    return

  }

}

wrappedWillStop()

wrapped版本构造冲突方法如下：调用willStop并把自己传进去。如果willStop认为wrapped会停止，那么就执行一个死循环。 如果willStop认为wrapped不会停止，就直接返回。

通过上述的方法，我们就知道willStop这样的函数肯定是无法被实现的；也就是停机问题无解。

03 | 程序的执行：相比 32 位 64 位的优势是什么？

【问题】 CPU 中有没有求对数的指令？如果没有那么程序如何去计算？

【解析】 CPU 中求一个数字的 2 倍，可以通过左移指令。比如 10 代表数字 2，左移 1 位变成 100 就代表数字 4。CPU 提供了乘法指令，所以如果求一个数字的幂，比如 33，可以拿 3*3 再乘以 3，需要计算 2 次。

但是如果求 3100 次方，就不会去计算 100 次。比如你可以先计算出 325，然后再求 (350)2，就是 3100。所以这样就节省了 1 倍的运算。

我举例主要是想告诉大家，CPU 没有提供很复杂的指令，但是这里有很多算法可以降低我们的时间开销。

然后我们来说说求对数，求对数也是没有指令的。因为对数是指数的逆运算，当然我们可以利用乘法运算一点点尝试。比如计算 log_210，我们可以先尝试 32，再尝试 3.12 等等，一直找到以 2 为底 10 的对数。这其实是个近似算法。

另外，在这个问题上聪明的数学家提出了很多近似算法，提升了计算效率。具体这里比较超纲，面试通常只考到有没有求对数的指令，感兴趣的同学可以学习泰勒级数、牛顿迭代法等。

比如下面这个泰勒级数可以用来求以e为底的对数，可以进行相似运算。

【补充内容】1 位的 CPU 能操作多大的内存空间？

在 03 课时程序的执行中，有个问题我讲的不是很明白，在这里我们再讨论一下。

之前提到过 32 位机器只能操作小于 32 位的地址总线，这里其实讲的不太清晰，历史上出现过 32 位操作 40 位地址总线的情况。

接下来再和你探讨一个极端情况，1 位的 CPU 能操作多大的内存空间。

答案是：无限大。

比如说，地址总线 40 位，说明 CPU 上有 40 个引脚接了地址总线。CPU 只有 1 位，因此操作这 40 个引脚可以分成 40 步。每次设置 1 根引脚的电平是 0 还是 1。所以本身 CPU 多少位和能操作多少位地址总线，没有本质联系。但是如果需要分步操作，效率会低，需要多次操作，不如一次完成来得划算。 因此我们今天的设计通常不拿 32 位 CPU 操作 40 位地址总线，而是用 64 位 CPU 操作。

04 | 构造复杂的程序 : 将一个递归函数转成非递归函数的通用方法？

【问题】 假设你使用的程序语言不支持递归程序，如果要求用栈来模拟下面这个斐波那契求第 n 项的程序，应该如何转换成等价的基于栈的非递归实现？

int fib(int n) {

 if(n == 1 || n == 2) { return n; }
  return fib(n-1) + fib(n-2)

【解析】其实这道题目等同于递归的函数如何非递归表达？改写斐波那契数列第 N 项目。

下面是我的一个伪代码，需要实现一个 Stack。

fib(n) {

  stack = new Stack();

  // 构造Stack

  // stack中每一项是一个Record

  // Record第一项是数据（参数或者返回值）

  // Record第二项是递归方向(down=1代表向下，up=2代表向上)

  stack.push((n, down));

  // stack中只有一项的时候递归停止

  while(stack.size() > 1) {

    (n, phase) = stack.pop();

    if(phase == down) {

      if(n == 1 || n == 2) {

        stack.push((1, -))

        continue

      }

      stack.push((n-1, down))

      stack.push((n-1, up))

    }

    else {

      last1 = stack.pop()

      last2 = stack.pop()

      stack.push((last1[0] + last2[0], up))

    }

  }

  return stack.pop()[0];

}

05 | 存储器分级 ：SSD、内存和 L1 Cache 相比速度差多少倍？

【问题】 假设有一个二维数组，总共有 1M 个条目，如果我们要遍历这个二维数组，应该逐行遍历还是逐列遍历？

【解析】 二维数组本质还是 1 维数组。只不过进行了脚标运算。比如说一个 N 行 M 列的数组，第 y 行第 x 列的坐标是： x + y*M。因此当行坐标增加时，内存空间是跳跃的。列坐标增加时，内存空间是连续的。

当 CPU 遍历二维数组的时候，会先从 CPU 缓存中取数据。

关键因素在于现在的 CPU 设计不是每次读取一个内存地址，而是读取每次读取相邻的多个内存地址（内存速度 200～300 CPU 周期，预读提升效率）。所以这相当于机器和人的约定，如果程序员不按照这个约定，就无法利用预读的优势。

另一方面当读取内存地址跳跃较大的时候，会触发内存的页面置换，这个知识在“模块五：内存管理”中学习。

总结

以上这些练习题你做得怎么样呢？我看到很多同学在留言区写下了练习题答案、思考过程以及课后总结，当然还有很多同学提出了问题。有问题是好事，说明你在认真思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。