0%

大话计算机里的“整数”2^n

人一般都有十个手指因而产生了最熟悉的十进制记数,计算机的结构先天性决定了它只能用二进制的记数。于是在此基础上总有一些运算方式和数字表示与2^n挂上钩,下面将尝试解释其中某些现象背后的机理

缓冲区长度的奥妙

不论是串口缓冲区还是网络通信的缓冲区,似乎总是随便设的一个大小总是对2^n情有独钟,究其原因其实还是有的(当然不排除真的是随便给的缓冲区长度)。如256或者1024等长度写成二进制其最高位总是为1,这就可以让擅长二进制位判断的硬件去根据缓冲区元素索引判断是否溢出。

当然最典型的还是利用其特性简化运算。例如在环形缓冲区中通常会有求余的操作,因为这样可以让指针在到达末尾处返回0。不巧的是,在早期的平台中指令集里面是没有求余操作的单个指令(当然现在都有)。即使不考虑性能这种为了求余而多增加一段程序也是不太优雅的,于是有人提出了替代求余的方案:如果我们将缓冲区的长度设定为256,那么索引值对256求余实际上等价于把索引值的第9个二进制位置零,于是我们可以采用一条与指令完成求余。这种巧妙的处理方法被作为一种习惯流传,至今在很多缓冲区的设计中都有出现。

乘除法与移位

在我们常见的十进制内完成同进制数的乘法(乘以10)只需要在乘数后面补零,乘以10^n只需要补n个零在末尾即可。同样地,在二进制里面,乘法与除法只是在二进制数的低位补或者删0,这种操作相当于将二进制数进行左移或者右移,而这种操作在对应的硬件上是容易实现的。所以我们会看到所有指令集无一例外地都有移位操作的指令。

在过去没有乘法指令的时候,定点数乘除法运算的实现往往依靠的是加/减法和移位。如果留意过CORDIC系列算法的实现,实际上乘法就是将乘数拆分为多个2^n之和(对应二进制位为1),通过分别对被乘数移相应的n-1位后求和。例如1010乘以0011,由于1010只有第4位与第2位为1,因此乘法的计算结果就是0011左移3位与其左移1位之和。

从定点到浮点

当我们尝试使用定点整数去表示各种小数时,总会遇到范围过窄的问题。实际上,计算机内数字的表示范围和精度是一对矛盾,当精度提升之后必然会引起范围的下降。根本原因在于二进制数与具体数字的映射关系总是唯一的,如32位数总是只能有2^32中可能表示的数字。

其中一种表示小数的解决方法是,默认每一个整数都要除以2^n以表示真实数字,这也是一种定点运算的方式。例如Q15或者Q31格式,将16位整数或32位整数均匀地映射至-1至1之间(最高位为符号位)。

当然更容易理解的方法是采用IEEE 754标准定义下的浮点数。所谓浮点是指小数点可变,这就意味着固定位数的数字可以表示出可变范围数字。这种浮点表示的具体方法有点类似固定小数位数的科学计数法,如32位浮点数中只记录符号位,小数m(范围0-1),指数exp,则真实数字可以表示为

这种表示方式确实可以表示出很大的数字,但是正如上述所说,范围增大了精度也必然会下降。相比于定点映射各种小数,浮点数本质上是一种非线性的映射关系,在0附近浮点数对数轴的映射是最密集的,而远离0精度则会变得极低。

如果是三年前的我,看到指数的底数为2是十分不解的,想着如果按照科学计数法以10为底数应该会更加符合人的直观印象。但是现在我看到以2为底数却是认为是相当合理,甚至是自然而然的,因为2^n总是可以用移位。比如说浮点数的乘法中,实际上是尾数与尾数相乘,两个指数幂相加。但是两个24bit尾数相乘是可以最大有48bit的结果,显然是需要截断的,而以2为底数就可以轻易地通过移位将尾数截断。