好了，既然现在所有的读者都掌握了二进制数，处于同一水平，那么下面就来讨论在信息论的背景下二进制意味着什么。

信息论（名词）

即从数学的角度研究如何利用符号序列、脉冲序列或其他形式对信息进行编码，以及信息能以多快的速度在计算机电路或者电信信道中传输。

根据信息论的观点，一个数值所包含的信息内容等于，为了在一个集合中唯一地确定这个数值，需要做出的二选一（是/否）决定的次数。

每个孩子都是应用信息论的专家

20个问题（20 Questions）这一游戏很好地阐释了信息内容这个概念。这种游戏的玩法是，第一个玩家随便在心里想一个东西，第二个（或其他）玩家通过提问来猜出这件东西，后者最多可提问20次。第一个玩家针对每次提问都用“是”或“否”来回答。

鉴于参加游戏的是小孩，我们会对这个游戏进行一些简单的修改，比如限定第一个玩家所想东西的范围（例如只能是动物），或者只有在得到了10次“否”的回答后，游戏才算结束（如果第二个玩家很快就猜出答案的话，第一个玩家可以撒谎或者改变所想的东西，这些都是允许的）。

这个游戏表明，要确定任意一个东西是什么，所需的信息量最多是20个二进制位。从数学的角度来看，如果所问的每一个问题都能排除一半的东西，那么20个问题事实上可以让提问者区分（即1048576）个东西。

这真是很多很多的东西了。

我们还可以更进一步。

考虑如下场景：有一个100平方英尺1英尺约合30.48厘米。——编者注的房间，地上铺了100块瓷砖，上面是拱形的天花板，靠近东面的窗户边有一张四柱大床，北面的墙边有一张古色古香的小写字台，而在床的西边则放着一个沉重的18世纪的衣橱。

你完全可以在一页纸上用JSON 或者其他你喜欢的脚本语言写出上面所有这些内容。

或者，你也可以采用下面这种略有不同的方法，用7个二进制位对地上的100块瓷砖进行编码，再用2个二进制位对4个主要方向进行编码，然后对3件家具进行编码，每件家具各用2个二进制位。按照瓷砖–家具–方向这样的顺序，你睡的床可以用10010100111来表示。（每个二进制位的“意义”这样的元信息，可以存在你的头脑中，或者编码到组装这个房间的软件中，抑或附在这些数据的后面。）

现在，描述整个房间只需要44个二进制位或者6个字节就够了，比起文字描述或者JSON文件，节省了相当多的空间（不仅我们这样认为，那些下载了你的游戏的移动端用户也会认同）。

简单来说，这就是一个数据压缩的过程。

假定有一个已经确定了范围且排好序的整数数组，比如说0~15，我们想找出数值10在这个数组中的位置。

二分查找算法的工作原理是这样的：首先将数组中的数据集分成两半，然后判断要找的数值10比处于中间位置的枢轴值是大还是小当然，如果一个数组包含偶数个元素，那么真正处于中间的元素是不存在的。这种情况下，可以根据喜好从中间偏左或中间偏右这两个元素中任选一个。。根据对比的结果，我们将数组分成了两半，并保留包含10的那一半数据进行进一步的查找。然后再次将10与新的枢轴值进行比较，并继续将数组分成两半。一直这样进行下去，直到最终只剩下我们要找的数值10。（如果这听上去与前面所说的20个问题游戏有些相似，那是因为事实确实如此！）

在查找的过程中，每当我们比较枢轴值与要查找的值的大小时，不妨输出一个二进制位来表示我们所做的决定（约定用0表示小于，用1表示大于）。

实际操作更便于理解，下面就实际操作一遍，具体如图2-1所示。

图2-1：在一个有限的数值范围内进行二分查找。如果将每一步所做的决定（选择大值端还是小值端）都保存下来，最终就会得到要查找的数值的二进制形式

这里最终的输出值是二进制值1010，这个值很有意思，它恰好是我们要查找的数值10的二进制形式。对元素个数等于的数据集，我们通过记录为了明确描述一个数，做了多少次“是”或“否”的决定，来表示这个数。

　如果你希望能在聚会中独处，不妨试试与其他人讨论这个话题。我敢肯定，这样做之后，你很快就会成为那个很尴尬的人。

可以看到，给定任意一个整数，我们都能将它转换为二进制形式。然而令人遗憾的是，给定一个整数，如果不经过二进制转换这一过程，我们很难直接知道它需要占几个二进制位。转换过程很无趣，但好在数学家已准备了下面的公式，让我们可以更轻松地处理这个问题很抱歉又用到了数学，不过这是理解后面的内容所必需的。：

表示一个数所需要的二进制位数

从数学上来说，lb将产生一个浮点数，例如，lb(10) = 3.321。

然而，从技术角度来说，由于现代的计算机硬件无法表示3.321个二进制位（这是因为二进制位已经是数据的最小单位，我们能使用的最小的二进制位数就是1），因此我们必须对这个值向上取整，也就是使用向上取整函数，即ceil（或ceiling）函数，从而将上面的公式更新为下式（由于这是一个更整洁的版本，因此我们决定用大写字母来表示，以示区别）：

不过，这又产生了另外一个问题，因为从技术上来说，如果一个数正好是2的幂，那么通过这一公式所得的结果要比实际需要的二进制位数小1。

下面以2（或者任何其他2的幂）为例：

可以看到，从数学上来说，上面计算的结果都正确，但实际上在计算机系统中表示2（二进制为10）和4（二进制为100）分别需要2个和3个二进制位。因此，还需要对上述公式做一些修正，以确保在遇到2的幂这些特殊的数时所得的结果还是正确的。

为了让你更清楚地理解这一概念，我们来看下表，其中展示了关于LOG2的一些很有趣的数据，以及用二进制表示相应的数所需的二进制位的数量。

因此，给定任意一个十进制整数，通过计算它对应的LOG2函数的值，我们就能知道用二进制来表示这个数最少需要多少二进制位。香农将一个变量对应的LOG2函数的值定义为它的熵（entropy），也就是用二进制来表示这个数所需的最少二进制位数。

数值的LOG2表示形式虽然高效，但对于制造计算机元件的方式来说并不实用。

这其中的问题在于，如果用最少的二进制位数来表示一个数，在解码相应的二进制字符串时会产生混乱（因为我们并不知道该数对应的LOG2长度），会与硬件的执行性能相冲突，两者不能兼顾。

现代计算机采用了折中的方案，用固定长度的二进制位数来表示大小不同的整数。最基本的存储单元是一个字节，由8个二进制位组成。在现代编程语言中，通常可用的整数的存储类型包括：短整型16个二进制位、整型32个二进制位、长整型64个二进制位。因此，对于十进制数10，虽然其对应的二进制数为1010，但在实际存储中是短整型，在计算机中的实际表示为0000000000001010。显然，这样做浪费了很多的二进制位。

这里需要指出的是，在现代应用程序开发中，我们所用到的绝大多数算法使用预先设定好的固定的二进制位长度，而不是通过LOG2函数计算出的二进制位长度。这就是信息论与实际实现层面的差别。在计算机内存中，我们遇到的任何二进制位流都会舍入到下一个字节对齐的大小。这可能会让人困惑，比如当我们只存储了7个二进制位的数据时，计算机仍然会报告说我们所存储的数据长度与计算机一次读取的最小字节数相同。

实际中的数据压缩目标，是尽可能接近理论上的压缩极限。这就是为了更好地学习和理解压缩算法，从而顺利掌握本书后面的内容，我们只从LOG2的角度去考虑问题的原因。

上一章目录下一章