陈凯

预设在记事本中有很多全部由0和1组成的字符串，可以进行如下步骤：搜索字符串中所有的“10”，并将“10”替换成“01”，反复执行此过程。那么，在若干次替换后，字符串中所有的“1”都会跑到字符串的右边，而“0”都会跑到字符串的左边。上一期文章提到，如果有一个二维的由0和1组成的字符串阵列，那么只要不停地执行全部替换，就可以实现给数据排序的功能。例如，可以把“5，4，8，1，2，3，6，4”——即纵列的“1”的个数，排序成为“1，2，3，4，4，5，6，8”。这种排序方法被称为珠排序（如图1）。

虽然实现原理很简单，但毕竟还是用到了记事本这个软件。实际上根据珠排序的原理，自己DIY一台专门用来进行数据排序的计算机也是很容易的，使用到的设备，仅仅是几个逻辑门电路和移位寄存器。如果手头没有门电路的元件，那么用逻辑门电路模拟器也能实现设计，笔者使用的是Logisim，可从网上免费下载到。

需要解决的关键问题是如何利用逻辑门，搜索出字符串中所有的“10”，使之变成“01”。在一个字符串中搜索数据，首先，需要取出字符串中第一个和第二个数字，把数字输入到变量中；其次，匹配两个变量的值是否是“1”和“0”，若是则把两个变量的值重置为“0”和“1”，若不是则不用重置；再次，继续取出后续的数字进行匹配。如此多的步骤，实现起来似乎相当复杂，但实际上，只需要四个逻辑门，就可以完成任务。

这个装备需要用到与门和异或门两种逻辑门，与门的作用是当两个输入端均为1的时候，则输出为1，否则输出为0，用符号表示。异或门的作用是当两个输入端输入的值不相等时，输出为1，若两个输入端输入的值相等，则输出为0，用符号表示。

电路有三个输入端，一个输出端，用一个实际的例子能够更好地说明这个逻辑电路的作用（如下页图2）。假设初始值是“101”，首先，第一个初始数值“1”和第二个初始数值“0”进行逻辑门的与操作，得到中间结果A是“0”；其次，第二个初始数值“0”和第三个初始数值“1”进行逻辑门的与操作，得到的中间结果B是“0”；再次，第一个初始数值“1”和中间结果A即“0”作异或操作，得到的中间结果C是“1”；最后，中间结果C“1”和中间结果B“0”作异或操作，得到的结果是“1”。于是输入初始值“101”，得到结果为1。

不妨再来一个例子，假设初始值是“011”，首先，第一个初始数值“0”和第二个初始数值“1”进行逻辑门的与操作，得到中间结果A是“0”；其次，第二个初始数值“1”和第三个初始数值“1”进行逻辑门的与操作，得到的中间结果B是“1”；再次，第一个初始数值“0”和中间结果A即“0”作异或操作，得到的中间结果C是“0”；最后，中间结果C“0”和中间结果B“1”作异或操作，得到的结果是“1”。于是输入初始值是“011”，得到结果为“1”。

大家也许会说，在这里可一点也看不出“1”和“0”对调位置的效果。别着急，想象一下，如果对字符串“101”作“将10变为01”的替换，那么这个字符串会变成“011”，中间那个数字是“1”。如果对字符串“011”作替换，那么这个字符串仍然是“011”，中间那个数字仍然是“1”。上面的那个逻辑电路的作用，就是把三个数字作为一组，计算出搜索和替换后中间那个数值的值。

例如，字符串“1011001101011110”，如果我们想要将字符串中的“10”变成“01”，可以先把整个字符串首尾各补一个“0”，使其变成“010110011010111100”，则可以把字符串放进一个移位寄存器中（如图3）。首先，逻辑电路获得的数据是“010”，逻辑运算后得到结果是“0”；接着，移动一位，输入的数据是“101”，得到的结果是“1”；然后，再移动一位，输入数据是“011”，得到的结果仍然是“1”，以此类推。整个数据全部经逻辑电路运算后，得到的字符串就是“0110101010111101”，把初始字符串和经逻辑运算后的字符串并列排放，我们就能看出替换的效果了（如图4）。

初始字符串：1011001101011110

结果字符串：0110101010111101

既然能够对一行字符串进行替换操作，那么对多行的字符串进行替换操作其原理也完全相同。这样的话，就能很容易打造出一个实体的排序计算机，所需要的仅仅是两种逻辑门和若干移位寄存器。

实际上，科学家对这样的字符串替换模型投入了不少精力，稍加改造就可以使之成为一个计算公路畅通程度的模型，因为“10”逐渐变成“01”的过程，和高速公路堵车时发生的状况很类似。另外，还可以将这个模型当成一个循环元胞自动机来使用。仅仅是对调字符串中数值的位置，就可以引出如此多有趣的研究内容，实在让人惊叹，对此有兴趣的朋友可自行深入探索其中更多的奥秘。