为了爱情，我发明了一个算法

1

张大胖和张二妮异地恋，见一面很不方面，两人只能通过电脑联系，可是由于计算机之间的通信（无线通信，光纤，双绞线等）存在信道干扰， 他们发送的消息经常出问题。

这一天，张二妮收到了一条张大胖发了的奇怪消息：

J LOWE YOV

这是什么意思？

张大胖看到张二妮迟迟没有回复，又发了两遍，这次张二妮那边收到的消息是：

I HRVE YPU

I LOVF WOU

张二妮把三条消息连起来看， 她发现，第一个位置字符 I 出现的频率最高，第二个字符L出现的频率高，第三个是O，第四个是V ...... 她终于猜出来了张大胖的心思：I LOVE YOU

2

两人周末见了面，聊起上次那让人抓狂的消息， 张二妮不满地说：“你发一堆乱七八糟的数据让我猜，想让人家当数学家啊！”

张大胖不好意地挠挠头：“这网络太差了，几个单词都出错 ！不过我也明白了一个道理，通过重复发送能消除不确定性。”

张二妮说：“这怎么行？！你学计算机的，想个办法啊！”

张大胖说：“这样吧，我们搞一个错误检测的办法，以后每次我给你发送一个消息的时候，都附加上一个校验和(checksum)，比如我想给你发4个数字 4 5 7 9 。”

张二妮马上打断他：“啊？难道你以后只想给我发数字了吗？”

“不是不是，我就是举个例子而已，其实计算机的所有东西都是二进制数字表示的，这个校验和是这么计算的，我把他们加起来4+5+7+9 = 25，保留个位就是5， 我把它放到消息的最后一并发给你：4 5 7 9 5。”

张二妮说：“奥，我明白了，我收到消息以后，把前面的几个数也累加起来计算校验和，然后和5比较，如果相等，数据就是对的，如果不相等，就是错的，我就不用去搭理它了，对吧？”

张大胖发送的消息：4 5 7 9 5

张二妮收到的消息：4 5 785

由于数据从9变成了8 ，张二妮再次计算校验和，就是4（只保留个位），和原来的不相等，表示出错。

张大胖说：“真聪明！”

可是张二妮眼珠一转，马上问道：“如果发生了这样的情况呢？”

张大胖发送的消息：4 5 7 9 5

张二妮收到的消息：46785

两个数据发生了变化，一个减1， 另外一个加1， 校验和还是5！错误检测不出来了！

张大胖叹了口气：“唉，看来这个求和算法太简单了，我得找到一个算法，得产生足够的混乱性和随机性才行。”

3

又是一个周末，两人见了面，互诉相思之苦以后，张大胖说：“我已经找到办法了，用除法。”

“什么除法？”

“就是把要发送的消息转换成一个巨大的二进制数，然后用咱们俩协商好的二进制数字去除，并从中得到余数。把这个余数当成校验和，与消息一并发送。你收到以后也用同样的除法除一下，验证校验和就行了。”

张二妮问道：“我对二进制加法略知一二，这除法怎么弄啊？！”

张大胖说：“很简单，和10进制除法是一样的，只不过出现借位的时候，借1不当作十，当作2就可以了。”

这样，checksum就是那个余数 100 ，发出去的消息就是 1001100 100。

张二妮用同样的除法一计算，核对一下余数是不是相等，就知道数据有没有错误了。

这时候张大胖突然想到了一个问题，用计算机来实现借位除法可不容易啊，必须得简化，反正就是为了得到一个余数吗，搞那么复杂干嘛，使用异或运算！

1 xor 0 = 1

1 xor 1 = 0

0 xor 1 = 1

0 xor 0 = 0

简单来说，就是“同性”相斥（结果为0），“异性”相吸（结果为1）

把这个异或运算用到除法中来，是这个效果：

张二妮都看傻眼了，她说：“刚才的除法我就做不了，你现在又弄什么XOR，太复杂了，我可算不出来。”

张大胖说：“别担心，我写个程序，会自动实现这个算法，到时候你直接用就行了。”

（码农翻身老刘注：这种办法就是大名鼎鼎的CRC的基本原理了，不过CRC做了额外的操作，对被除数的低位补了若干个0（除数长度-1）， 然后再做除法，得到的余数作为checksum发送， 而接收方用同样的除数做除法，如果发现余数为0，则数据正确。感兴趣的同学可以自己手工计算一下。CRC背后数学原理就有待大家去进一步研究了。）

4

CRC算法运转得还不错，过了两周，张二妮提出了新的问题：“你这个算法只能发现错误，出了错误还得重传，你能不能想个办法，自动地就纠正错误？”

张大胖：“这个..... 你让我想想吧。”

张大胖怎么才能纠正错误？我们拭目以待。

后记：

校验和是数据传输中重要的检测错误的手段，是一个非常基础的算法，既有相对简单的累加，如TCP：

也有复杂的CRC，例如以太网的数据帧，校验和有32位。

关于作者：刘欣，码农翻身公众号作者，畅销书《码农翻身》作者，近 20 年软件行业从业经验，前 IBM 架构师，领导过多个企业应用架构设计和开发工作；洞察技术本质，用故事讲解技术是拿手好戏。