免费电子书《使用开源软件-自己动手写操作系统》Revision 2 发布

免费电子书《使用开源软件-自己动手写操作系统》的主页在：http://share.solrex.cn/WriteOS/ ，您可以到这里下载 pdf 格式电子书和随书源代码。

2008 年 2 月 21 日发布第一版，拖了十个月我才发布了第二版。虽然有一些懒惰的原因在里面，但更重要的原因是没有很多可以大块利用的时间。从开始动手，才知道写书是一件非 常痛苦的工作，尤其是有代码的书。再加上本书目前的主要代码都是汇编语言，一旦出错就要花好长时间调试，代码运行正确了，要在不同的 Linux 进行编译以确保能正确通过，又要加注释、除去冗余指令，代码的工作结束就要接着关注排版、查资料、填补内容、做插图，总之写一天书下来我累得精神都会振奋 不起来。

本来打算十月底就发布第二版，但是因为研究工作稍微耽误了一下，就又拖到了十一月底，总之我还是完成了这一章。这一版虽然只增加了第三章，但页码却 从 40 页增加到了 104 页，示例代码也从 2 个增加到 10 个，与第一版的工作量不可同日而语。由于这一版的发布周期过长，我在按版本发布的基础上增加了每周发布，也因此在编写过程中得到了不少帮助。

这本书从计划开始就得到很多朋友的肯定，在编写的过程中也得到了很多朋友的帮助。不计刚发布第一版时几乎每天一千次的下载量，从 2008 年 5 月 9 号把所有源代码迁移到 Google Code 项目后，加上每周发布，就有共计两万一千多次下载。我非常感谢大家对我一如既往的支持，感谢那些在我的博客评论或者发电子邮件给我打气的朋友，尤其感谢那 些在邮件中或者错误报告页中指出本书错误或者提供很好建议的朋友！

我尤为高兴的是听一位朋友说北京邮电大学某位教授操作系统课程的老师向同学推荐这本电子书，这正与我写这本书的初衷相合，就像我在前言中所说：

本书的最终目标是成为一本大学“计算机操作系统”课程的参考工具书，为学生提供一个step by step 的引导去实现一个操作系统。这不是一个容易实现的目标，因为我本人现在并不自信有那个实力了解操作系统的方方面面。但是我想，立志百里行九十总好过于踯躅不前。

我将继续努力将这本书写下去，也希望大家能够继续对这本书保持关注，并帮助我完善此书。下面是本书这次发布的章节信息，如果您发现本书中的错误（那是不可避免的），或者有更好的建议，请您一定到本书的错误报告页指出，兄弟我将非常感谢！第三章进入保护模式

3.1 实模式和保护模式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1 一段历史. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.2 实模式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.3 保护模式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.4 实模式和保护模式的寻址模式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 与保护模式初次会面. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.1 GDT 数据结构. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2.2 保护模式下的demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.3 加载GDT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.4 进入保护模式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.5 特别的混合跳转指令. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.6 生成镜像并测试. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3 段式存储. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.1 LDT 数据结构. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.2 段描述符属性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.3 使用LDT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.4 生成镜像并测试. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.3.5 段式存储总结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4 特权级. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.1 不合法的访问请求示例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.4.2 控制权转移的特权级检查. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.3 使用调用门转移. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.4 栈切换和TSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5 页式存储. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.5.1 分页机制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.5.2 启动分页机制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.5.3 修正内存映射的错误. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5.4 体验虚拟内存. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.6 结语. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

统计二进制中 1 的个数

这是一道《编程之美－微软技术面试心得》中的题目，问题描述如下：

对于一个字节(8bit)的变量,求其二进制表示中"1"的个数,要求算法的执行效率尽可能地高。

《编程之美》中给出了五种解法，但是实际上从 Wikipedia 上我们可以找到更优的算法。

这道题的本质相当于求二进制数的 Hamming 权重，或者说是该二进制数与 0 的 Hamming 距离，这两个概念在信息论和编码理论中是相当有名的。在二进制的情况下，它们也经常被叫做 population count 或者 popcount 问题，比如 gcc 中就提供了一个内建函数：

int __builtin_popcount (unsigned int x)

输出整型数二进制中 1 的个数。但是 GCC 的 __builtin_popcount 的实现主要是基于查表法做的，跟编程之美中解法 5 是一样的。Wikipedia 上的解法是基于分治法来做的，构造非常巧妙，通过有限次简单地算术运算就能求得结果，特别适合那些受存储空间限制的算法中使用：

/* ===========================================================================
* Problem:
*   The fastest way to count how many 1s in a 32-bits integer.
*
* Algorithm:
*   The problem equals to calculate the Hamming weight of a 32-bits integer,
*   or the Hamming distance between a 32-bits integer and 0. In binary cases,
*   it is also called the population count, or popcount.[1]
*
*   The best solution known are based on adding counts in a tree pattern
*   (divide and conquer). Due to space limit, here is an example for a
*   8-bits binary number A=01101100:[1]
* | Expression            | Binary   | Decimal | Comment                    |
* | A                     | 01101100 |         | the original number        |
* | B = A & 01010101      | 01000100 | 1,0,1,0 | every other bit from A     |
* | C = (A>>1) & 01010101 | 00010100 | 0,1,1,0 | remaining bits from A      |
* | D = B + C             | 01011000 | 1,1,2,0 | # of 1s in each 2-bit of A |
* | E = D & 00110011      | 00010000 | 1,0     | every other count from D   |
* | F = (D>>2) & 00110011 | 00010010 | 1,2     | remaining counts from D    |
* | G = E + F             | 00100010 | 2,2     | # of 1s in each 4-bit of A |
* | H = G & 00001111      | 00000010 | 2       | every other count from G   |
* | I = (G>>4) & 00001111 | 00000010 | 2       | remaining counts from G    |
* | J = H + I             | 00000100 | 4       | No. of 1s in A             |
* Hence A have 4 1s.
*
* [1] http://en.wikipedia.org/wiki/Hamming_weight
*
* ===========================================================================
*/
#include <stdio.h>

typedef unsigned int UINT32;
const UINT32 m1  = 0x55555555;  // 01010101010101010101010101010101
const UINT32 m2  = 0x33333333;  // 00110011001100110011001100110011
const UINT32 m4  = 0x0f0f0f0f;  // 00001111000011110000111100001111
const UINT32 m8  = 0x00ff00ff;  // 00000000111111110000000011111111
const UINT32 m16 = 0x0000ffff;  // 00000000000000001111111111111111
const UINT32 h01 = 0x01010101;  // the sum of 256 to the power of 0, 1, 2, 3

/* This is a naive implementation, shown for comparison, and to help in
* understanding the better functions. It uses 20 arithmetic operations
* (shift, add, and). */
int popcount_1(UINT32 x)
{
  x = (x & m1) + ((x >> 1) & m1);
  x = (x & m2) + ((x >> 2) & m2);
  x = (x & m4) + ((x >> 4) & m4);
  x = (x & m8) + ((x >> 8) & m8);
  x = (x & m16) + ((x >> 16) & m16);
  return x;
}

/* This uses fewer arithmetic operations than any other known implementation
* on machines with slow multiplication. It uses 15 arithmetic operations. */
int popcount_2(UINT32 x)
{
  x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
  x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
  x += x >> 8;           //put count of each 16 bits into their lowest 8 bits
  x += x >> 16;          //put count of each 32 bits into their lowest 8 bits
  return x & 0x1f;
}

/* This uses fewer arithmetic operations than any other known implementation
* on machines with fast multiplication. It uses 12 arithmetic operations,
* one of which is a multiply. */
int popcount_3(UINT32 x)
{
  x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
  x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
  return (x * h01) >> 24;  // left 8 bits of x + (x<<8) + (x<<16) + (x<<24)
}

int main()
{
  int i = 0x1ff12ee2;
  printf("i = %d = 0x%x\n", i, i);
  printf("popcount_1(%d) = %d\n", i, popcount_1(i));
  printf("popcount_2(%d) = %d\n", i, popcount_2(i));
  printf("popcount_3(%d) = %d\n", i, popcount_3(i));
  /* If compiled with other compiler than gcc, comment the line bellow. */
  printf("GCC's  __builtin_popcount(%d) = %d\n", i,  __builtin_popcount(i));
  return 0;
}

使用 Synergy 在主机间共享鼠标和键盘

作者：杨文博 < http://blog.solrex.cn >
地址：http://blog.solrex.cn/articles/share-keyboard-and-mouse-with-synergy.html

今天我使用了一个让我感觉非常震撼的软件：Synergy，相见恨晚！

简单地来说，这个软件的功能是在 n 台电脑间共享同一个电脑上的鼠标和键盘。和扩展桌面不同，扩展桌面是一台主机拖两台以上的显示器，这个软件是用一套鼠键控制两台以上的主机。（我曾经见到过一个医学仪器用的 IBM 的键盘，可以控制几台工作站，貌似是几万块。）

像我们计算机科学的学生，一般来说都会有两台电脑。比如我自己，实验室一台台式机，自己一台笔记本，当我把笔记本电脑拿到实验室的时候，总会发愁把 我的笔记本外接键盘和外接鼠标放在哪里（我不喜欢用笔记本自带键盘，用外接键鼠我就可以半躺在椅子靠背上打字）。手底下放着两个键盘和两个鼠标，总要想一 想我现在要用哪个。通过这个小软件，我的笔记本和台式机可以共用台式机的键盘，这样我就不必注意我到底在用哪台机器的键盘和鼠标了，感觉好爽！

还有一个非常牛的特性就是：支持共享剪贴板。因为大部分程序员使用两个以上的显示器是为了写代码的同时在另一个 显示器上翻看文档或者网页，我们使用两台以上电脑的作用也在于此。如果两台电脑之间可以共享剪贴板，再加上 NFS 或者 Samba，那么在大部分情况下来说，这和一台电脑拖两台显示器没任何区别了（也许更方便，比如你可以一端跑 Linux，一端跑 Windows）。

关于这个软件的介绍可以见下面两篇博客：用 Synergy 共享两台电脑的键盘鼠标 和 用 Synergy 共享鼠标键盘。

需要解释一下使用 Synergy 时容易引起混淆的概念： Server 是指被共享鼠标键盘的主机，比如我就是使用台式机作为 Server；Client 是指使用 Server 的鼠键的主机。

使用 QuickSynery 时也要注意：Server 端 QuickSynery 需要指定 Client 主机在哪个位置，比如我希望笔记本在左面，就在左面填入笔记本的主机名，但不需要指定 Server IP；Client 端 QuickSynery 只需要指定 Server IP，但不需要选择机器的相对位置；另外，在尝试连接不成功后，一定要杀死后台所有 synery 进程，最好用命令行启动 quicksynery 通过屏显来查找错误。

QuickSynery 的最新版本是 0.8，Ubuntu 仓库中版本是 0.6，如果您使用 QuickSynery 过程中出现错误或者希望使用更新的版本，可以到我的共享网站上下载我自己编译打包的 QuickSynery 0.8: http://share.solrex.cn/ibuild/quicksynergy_0.8_i386.deb 。

从一个数列中取具有最小和的子序列

问题描述：给定一个含有 n 个元素的数列，元素有正有负，找出和最小的一组相邻的数。即给定 a[n]，求 i,j 使得 a[i] + a[i+1] + ...+ a[j] 的和最小。

这个问题并不难，但是我在想这个问题时经历了比较有趣的思考过程，写下来给大家分享一下。

其实这道题主要考察的是问题转换（或者说是抽象？）的能力，即如何将一个看似复杂的问题转换成一个简单的问题。直接求一个连续子列的和看起来很麻 烦，我们要考虑 i 和 j 的取值，然后把子列中的元素加起来。但是换一个角度，一个连续子列的和可以看成是两个前缀和相减，比如：a[i] + a[i+1] + ...+ a[j] 实际上就等于 s[j] - s[i-1]，其中 s[k] = a[0] + a[1] + ... + a[k]。这在高等数学中也是会被经常用到的方法。

所以我们要做的就是

计算出前缀和序列 s[n]，并找出最小的 s[j] - s[i]，其中 j>i，且 j,i 属于 {0,1,...,n}。

如果不要求 j>i，那么答案很简单，s[n] 中最小值减去最大值就是结果。但既然要求了 j>i，就不能这样做了，因为最小值的位置未必在最大值后面。最显而易见的方法就是遍历了：

J = 1; I = 0;
for (i=0; i<n; i++) {
  for (j=i+1; j<n; j++) {
    if (s[j] - s[i] < s[J] - s[I]) {
      I = i; J = j;
    }
  }
}

但是这个算法很耗时，两层嵌套，等差数列求和，复杂度肯定是 O(n²)。观察一下数列的规律我们可以发现，如果 s[i] < s[I] 的话，我们就没有必要计算 s[j] - s[i]，因为结果肯定比 s[j] - s[I] 大嘛，同理可以用于 s[j] > s[J] 的情况，这样呢，我们可以稍微优化一点儿：

J = 1; I = 0;
for (i=0; i<n; i++) {
  if (s[i] < s[I]) continue;
  for (j=i+1; j<n; j++) {
    if (s[j] > s[J]) continue;
    if (s[j] - s[i] < s[J] - s[I]) {
      I = i; J = j;
    }
  }
}

但是这个优化作用到底有多大？我没有仔细计算，是比第一种情况快了一点儿，但最显著的速度提升还是在于第一层循环中，那样就能减少 n-i+1 次计算，在最坏的情况下仍然是 O(n²)。所以我觉得仍然不够，不就求一个最小值嘛，为什么那么慢呢，肯定是因为我笨。于是我就在 BBS 求助了一下别人，果然有人给出更快的算法：

J = 1; I = 0; max = 0;
for (i=1; i<n; i++) {
  if (s[i]-s[max] < s[J]-s[I]) {
    I = max;  J = i;
  }
  max = s[i] > s[I] ? i : max;
}

这个算法的思想是： s[I] 肯定是 s[J] 之前最大的数，s[J] 也是 s[I] 之后最小的数，那么保留到目前为止最大的数 s[max]，用当前数 s[i] 去减它（肯定是小于 s[i] - s[I] 的），看它是否小于 s[J] - s[I]，如果是的话，那么 s[i] -s[max] 就是到 i 为止最小的差值对。扫描一遍 s[n] 就能得到结果，O(n)！

定制自己的 Gnome 登录窗口主题

作者：杨文博 < http://blog.solrex.cn >

地址：http://blog.solrex.cn/articles/diy-gnome-login-window-theme.html

摘要：很多人（包括我）经常取笑 Ubuntu 的默认主题叫做"屎黄色的 Ubuntu"，孰不知 Ubuntu 的主题也可以很好看。本文就教您如何修改 Ubuntu 默认 Gnome 桌面的登录主题。本文适用于那些喜欢美化操作系统的 Linuxer，尤其是那些希望通过美化系统讨女孩子欢心的 Linuxer。

常看我博客的读者会知道，我的很多文章都起源于讨女孩子喜欢的实际需要，这篇文章也是源起于此。我只是想把我和女友的照片放到登录屏幕上，发现只设 置为用户头像显示的太小了，于是就自己搞了一个 Gnome 的登录窗口主题（如右图所示），我家希希看了以后相当 happy。

其实自己做一个 Gnome 的登录主题非常简单，主要包括以下几个步骤：

1. 准备好一张背景图片和一个选项按钮图片

背景图片的制作才是整个过程中最难的地方。如果 Gimp 技术好，可以做出非常漂亮的背景。当然，像我这样的图片处理小白也不是没有办法，Google 的 Picasa for Linux 就是非常好的工具，我所用的背景图片就是用 Picasa 对照片进行简单处理得来的。至于 Picasa 怎么用？就超出本文的范畴了，相信仔细探索一下 Picasa 的选项，整合几张照片不是很困难的事情。一定要记住导出的图片应该跟屏幕分辨率大小相当，那样图片才不会变形。

选项按钮图片可以用自己做的矢量 svg 图形，或者只使用按钮，或者使用我提供的模板主题中的 options.svg。

2. 添加几个脚本文件

假设您已经做好的背景图片叫做 nju.jpg，选项按钮图片叫做 options.svg，那么您至少应该再添加两个脚本：nju.xml 和 GdmGreeterTheme.desktop，内容分别是：

$ more nju.xml

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE greeter SYSTEM "greeter.dtd">
<greeter>
  <item type="pixmap">
    <normal file="nju_love.jpg"/>
    <pos x="0" y="0" width="100%" height="0"/>
  </item>

  <item type="rect">
    <normal color="#FFFFFF" alpha="0.5"/>
    <!-- Input box postion -->
    <pos anchor="c" x="25%" y="80%" width="box" height="box"/>
    <box orientation="vertical" min-width="360" xpadding="30" ypadding="20" spacing="10">
      <item type="label">
        <pos anchor="n" x="50%"/>
        <normal color="#000000" font="Sans 16"/>
    <!-- Stock label for: Welcome to %h -->
    <stock type="welcome-label"/>
      </item>
      <item type="label" id="pam-prompt">
        <pos anchor="nw" x="10%"/>
        <normal color="#000000" font="Sans 12"/>
    <!-- Stock label for: Username: -->
    <stock type="username-label"/>
      </item>
      <item type="rect">
    <normal color="#000000"/>
        <pos anchor="n" x="50%" height="24" width="80%"/>
    <fixed>
      <item type="entry" id="user-pw-entry">
            <normal color="#000000" font="Sans 12"/>
            <pos anchor="nw" x="1" y="1" height="-2" width="-2"/>
      </item>
    </fixed>
      </item>
      <item type="label" id="pam-message">
        <pos anchor="n" x="50%"/>
        <normal color="#000000" font="Sans 12" alpha="0.5"/>
    <text></text>
      </item>
      <item type="label" id="pam-error">
        <pos anchor="n" x="50%"/>
        <normal color="#000000" font="Sans 12" alpha="0.5"/>
        <text></text>
      </item>
      <item type="label" id="caps-lock-warning">
        <pos anchor="n" x="50%" y="100%"/>
        <normal color="#FF0000" font="Sans 12" alpha="0.5"/>
    <stock type="caps-lock-warning"/>
      </item>
      <item type="rect">
    <pos x="90%" y="0"/>
    <fixed>
          <!-- Option button -->
          <item type="svg" button="true" id="options_button">
            <normal file="options.svg" alpha="0.51"/>
            <prelight file="options.svg" alpha="1.0"/>
            <pos x="19" y="-28" width="40" height="40"/>
          </item>
    </fixed>
      </item>
      </box>
  </item>
</greeter>

$ more GdmGreeterTheme.desktop

[GdmGreeterTheme]
Greeter=nju.xml
Name=NJU
Description=Nanjing University
Author=Solrex Yang
Screenshot=screenshot.png
Copyright=

上面代码中最关键的几点是：一、在 nju.xml 中，我们给出了背景图片的文件名 nju.jpg，选项按钮 options.svg 和登录窗口中登录框的位置和内容；二、在 GdmGreeterTheme.desktop 我们给出了登录窗口主题 xml 定义文件的文件名 nju.xml 和缩略图 screenshot.png。

3. 测试登录窗口主题

假设我们所有的文件都在 nju 目录下，那么我们就可以使用 gdmthemetester 来测试我们的主题能否显示正常了（Ubuntu 下需要先用 sudo apt-get install xnest 安装 xnest 软件包），然后根据显示情况调整登录框的位置。并且可以用截图工具截到屏幕截图 screenshot.png。

$ ls
nju
$ ls nju
GdmGreeterTheme.desktop  nju.jpg  nju.xml  options.svg
$ export XNESTSIZE=1024x768
$ gdmthemetester console nju

4. 安装登录窗口主题

我们已经测试过窗口主题，获得了所有文件，就可以将制作的窗口主题文件打包并安装了。

$ ls nju
GdmGreeterTheme.desktop  nju.jpg  nju.xml  options.svg  screenshot.png
$ tar -czvf nju.tar.gz nju

安装过程可以通过图形界面来做：System->Administration->Login Window->Local，然后将做好的安装包 nju.tar.gz 拖到 theme 选择窗口里，安装然后并在前面复选框中选择启动时使用该 theme 即可。

综上所述，可以看到写一个 Gnome 登录主题是非常简单的事情，难就难在怎么设计编排各个元素的位置。为了解更多的 theme 选项，读者可以自行去查看 Ubuntu 自带 theme 的源代码，在 /usr/share/gdm/themes/ 目录下。另外，在我的共享目录 http://share.solrex.cn/misc/nju.tar.gz 可以下载到本文中提供的模板主题。

今天小杨同学睡了一个大懒觉，九点多醒来和女朋友发了几条消息，一转身又睡着了。再醒来看表就到 12 点了，想起来约好 12 点半和某同学碰头一起去参加轮滑社团的活动，于是乎准备发条消息取消掉，忽然发现没有对方的号码。有约定不好食言呀，就挣扎着爬起来快速洗脸刷牙去吃饭， 总算按时和大部队集合了。

下午的主要活动就是轮滑了。今年第一次中科院玉泉、中关村和北郊校区的刷子们同时行动，目的地是奥体中心！从玉泉到中关村距离有 16 公里，虽然有几位猛男/女是刷过去的，对我来说还是太远了，所以还是老老实实坐公交到青年公寓。然后大家都换上鞋，30 多号人浩浩荡荡地就杀往鸟巢了，其实这也是我第一次刷街。

从青年公寓到鸟巢大约花了一个小时吧，然后在鸟巢附近的广场上玩了玩，到晚上撤退时已经累得不行了。社团一起在北郊一个叫做"孙记乡村驴肉馆"的小店吃了顿饭，您还甭说，味道还真不错，平均每人只花了二十多块，吃得饱饱的，也挺实惠。吃完饭实在没力气再滑，就坐 751 回来啦。

话说了这么多，言归正传，明天可是小杨同学的大日子。什么日子呢？就是我的 22 岁生日，当当当当，就是到法定结婚年龄啦(^_^)。其实也没什么大不了的，不过某小姑娘会小开心一下啦。

按照我的习惯，过生日时总喜欢在博客里感慨一番，不过今年呢......也不例外。

虽然没有达到我的设想，总的来说这一年还是做了一些事情。这学期开学以来，研究工作不是很顺利，到现在我仍然认为还没有进入状态，但也是有几个亮点 的，不至于对自己的工作全盘否定。生活方面对自己满意好多了，规律的作息和饮食，充足的体育锻炼，鼻炎仍然有困扰，但程度已经较上年减轻很多，这也是我乐 于感受到的。要说烦忧，谁能没有呢？就不足为外人道了。

唉，我发现最近一段时间技术类博客已经统领我的发文了，这是个不好的趋势，以后要注意和生活类的平衡，毕竟我希望这里成为一个我成长方方面面的记录。不过今天就写到这吧，要和某小姑娘开始聊天了 :)

用两个非门和任意的与、或门构造三个非门

计算机科学中有很多有趣的 puzzle，他们可能出现在那些自命清高的企业的笔试题中，也可能来源于在网路上不经意的一瞥。后者比如我在无意中遇到的 Jamie Zawinski 的个人主页：http://www.jwz.org/，他即是在著名的 Teach Yourself Programming in Ten Years 一文中，Peter Norvig 提到的那位：

One of the best programmers I ever hired had only a High School degree; he's produced a lot of great software, has his own news group, and made enough in stock options to buy his own nightclub.

Jamie Zawinski 的个人主页看起来就像是 hexdump 的结果，而且以某种规律变化着，比较奇怪的是其中埋藏的一些超级链接并不发生变化。Jamie Zawinski 在网页的源代码中这样写道：

<!-- mail me if you find the secret -->
<!--   (no, you can't have a hint)  -->

我徒劳无功地搜索了一下，没有找到任何明确的解答。如果您通过我这篇文章了解到这个 puzzle，并且解答了它的话，非常希望您也 mail 给我一份解答。

说了那么多，其实本文的主题 puzzle 却是来源于前者。这个问题更详细的阐述是：

假设有一个逻辑黑盒，三个布尔型变量 x, y, z 作为输入，输出三个布尔变量 X, Y, Z，其中：
X = ~x; Y = ~y; Z = ~z;
注意，~ 符号代表一个非门。请用两个非门和任意多个与、或门实现这个黑盒。

这个问题大概是在计算机硬件设计中提出来的，所以看起来貌似很"电子"，但是其基础却是计算机科学中的布尔代数运算。下面代码的注释中已经包含详细 的算法和分析，这里我就不再解释了。（当然，这个问题的答案不是我想出来的，我只是实现并分析了一下，作为我算法学习的笔记记录在此。）

/* ===========================================================================
* Problem:
*   Construct 3 NOT gates from only 2 NOT gates(and *no* XOR gates).
*
*   Assume that a logical blackbox has three Boolean inputs x, y, z and
*   three Boolean outputs X, Y, Z where the outputs are defined as:
*     X = ~x
*     Y = ~y
*     Z = ~z
*   Note that ~ stands for a NOT gate. Please realize this blackbox using
*   only two NOT gates, and as many as possible AND and OR gates.
*
* Algorithm I:
*   Internal Nodes:
*   r = (x & y) | (x & z) | (y & z);
*   R = ~r;
*   s = (R & (x | y | z)) | (x & y & z);
*   S = ~s;
*
*   Equations for Outputs:
*   X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
*   Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
*   Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));
*
* Analysis I:
*   We create 4 internal signals first: r, R, s and S. What equations above
*   say is that signal `r' will be 1 if two or three of the inputs are 1.
*   Meanwhile, signal `s' will be 1 if only one input is 1 or if all three
*   inputs are 1. The end result is that the two-bit word formed from `r'
*   and `s' tells us how many 1's we have[1]:
*   | r s | Means  |    | x y z | r s |    | x y z | r s |
*   |++++++++++++++|    |+++++++++++++|    |+++++++++++++|
*   | 0 0 | 0 Ones |    | 0 0 0 | 0 0 |    | 1 0 0 | 0 1 |
*   | 0 1 | 1 One  |    | 0 0 1 | 0 1 |    | 1 0 1 | 1 0 |
*   | 1 0 | 2 Ones |    | 0 1 0 | 0 1 |    | 1 1 0 | 1 0 |
*   | 1 1 | 3 Ones |    | 0 1 1 | 1 0 |    | 1 1 1 | 1 1 |
*
*   Thus now that we have the signals r and s (and their inverse
*   counterparts R and S), it's easy to construct any Boolean function of
*   x, y, and z, using only AND and OR gates:
*     X = (R & S) | (R & s & (y | z)) | (r & S & (y & z))
*   Proof:
*    1> x, y, z are all 0s, (R & S) = ~(r | s) = 1, obviously X=Y=Z=1, X = ~x;
*    2> (x, y, z) has at least one 1, R & S = 0, will be ignored, hence we
*       have:
*         X = (R & s & (y | z)) | (r & S & (y & z))
*    2.1> (x, y, z) has two or three 1s, R = ~r = 0, (R & s & (y | z)) = 0,
*         will be ignored, then we get:
*           X = S & (y & z)
*    2.1.1> (x, y, z) has three 1s, S = ~s = 0, obviously X=Y=Z=0, X = ~x;
*    2.1.2> (x, y, z) has two 1s, S = ~s = 1, will be ignored, hence we have:
*             X = y & z
*    2.1.2.1> (y, z) has one 1, x = 1, X = y & z = 1 & 0 = 0, X = ~x;
*    2.1.2.2> (y, z) has two 1s, x = 0, X = y & z = 1 & 1 = 1, X = ~x;
*    2.2> (x, y, z) has one 1, r = 0, (r & S & (y & z)) = 0, will be ignored,
*         we have:
*           X = y | z
*    2.2.1> (y, z) has one 1, x = 0, X = y | z = 1 | 0 = 1, X = ~x;
*    2.2.2> (y, z) has no 1s, x = 1, X = y | z = 0 | 0 = 0, X = ~x.
*    In conclusion, X = ~x for all cases.
*   QED.
*
* Algorithm II:
*   Internal Nodes:
*   _2or3_1s = ((x & y) | (x & z) | (y & z));
*   _0or1_1s = !(_2or3_1s);
*   _1_1     = _0or1_1s & (x | y | z);
*   _1or3_1s = _1_1 | (x & y & z);
*   _0or2_1s = !(_1or3_1s);
*   _0_1s    = _0or2_1s & _0or1_1s;
*   _2_1s    = _0or2_1s & _2or3_1s;
*
*   Equations for Outputs:
*   X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
*   Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
*   Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));
*
* Analysis II:
*   Almost the same as Analysis I.
*
* [1] http://www.edadesignline.com/howto/191600992
* ===========================================================================
*/

#include <stdio.h>

typedef unsigned int BOOL;

int main()
{
  int i, fail;
  BOOL x, y, z, X, Y, Z;
  BOOL r, R, s, S;
  BOOL _2or3_1s, _0or1_1s, _1_1,  _1or3_1s, _0or2_1s, _0_1s, _2_1s;

  /* ==================== Algorithm I ==================== */
  printf("Algorithm I:\n");
  fail = 0;
  for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    r = (x & y) | (x & z) | (y & z);
    //R = !r;                               /* #1 NOT gate. */
    R = ~r & 1;                             /* #1 NOT gate. */
    s = (R & (x | y | z)) | (x & y & z);
    //S = !s;                               /* #2 NOT gate. */
    S = ~s & 1;                             /* #2 NOT gate. */
    /* Output. */
    X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
    Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
    Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%u\n", x, y, z, X, Y, Z);
  }
  if (fail != 0) {
    printf("%d TEST FAILED!\n", fail);
  } else if (!fail) {
    printf("ALL TEST PASSED!\n");
  }

  /* ==================== Algorithm II ==================== */
  printf("Algorithm II:\n");
  fail = 0;
  for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    _2or3_1s = ((x & y) | (x & z) | (y & z));
    //_0or1_1s = !(_2or3_1s);               /* #1 NOT gate. */
    _0or1_1s = ~(_2or3_1s) & 1;             /* #1 NOT gate. */
    _1_1     = _0or1_1s & (x | y | z);
    _1or3_1s = _1_1 | (x & y & z);
    //_0or2_1s = !(_1or3_1s);               /* #2 NOT gate. */
    _0or2_1s = ~(_1or3_1s) & 1;             /* #2 NOT gate. */
    _0_1s    = _0or2_1s & _0or1_1s;
    _2_1s    = _0or2_1s & _2or3_1s;
    /* Output. */
    X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
    Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
    Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%u\n", x, y, z, X, Y, Z);
  }
  if (fail != 0) {
    printf("%d TEST FAILED!\n", fail);
  } else if (!fail) {
    printf("ALL TEST PASSED!\n");
  }
  return 0;
}