计算机舍入问题

84 阅读 0 评论 56 点赞

我是靠谱客的博主活力衬衫，最近开发中收集的这篇文章主要介绍计算机舍入问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最近在学习 CSAPP(2e) 的时候才第一次意识到计算机中的舍入也不是一个简单的内容。现做总结如下：

向整数舍入：

向整数舍入比较简单理解，直接去掉小数，仅取整数部分，对于正负数均是如此，正数向下舍入，负数向上舍入，因此我们可以说成向零舍入（round-to-zero）。

右移与除法的舍入问题：

在C语言中有一个右移运算符>>，一般说来，向右移1位相当于除以2，就像下面这样（k表示右移的位数，第二栏表示右移之后的值，第三栏表示实际运算结果）：

k	右移k位	12340/(2^k)
0	12340	12340.0
1	6170	6170.0
4	771	771.25
8	48	48.203125

可以看到对于无符号的数来说，右移k位和除以2^k来说结果是一样的。

但是如果问题扩展到有符号数，对于负数来说，结果可能会有点不一样了

k	右移k位	-12340/(2^k)
0	-12340	-12340.0
1	-6170	-6170.0
4	-772	-771.25
8	-49	-48.203125

从上表中可以看到，当右移8位的时候，得到-49，这与向零舍入的结果-48并不吻合。

右移总是向下舍入，而对于向零舍入的负数来说是向上舍入，因此为了保证结果吻合，需要进行一个偏置（biasing）。

对于负整数 x 和任意 y > 0 的y，x / y 向上舍入的结果和 ( x+y-1 ) / y 向下舍入的结果是相同，把 y = 2^k 带入向下舍入的公式有， ( x + 2^k -1 ) / 2^k，换算成C语言的移位表达式也就是

( x + (1 << k) - 1 ) >> k

这样就可以保证负数通过这么一个偏置，其“右移”的结果也是向上舍入。

总结起来，就是 x / (2^k) 等价的右移表达式为：

( x < 0 ? x + (1<<k) - 1 : x) >> k

IEEE浮点数舍入：

浮点数舍入相比向整数舍入，就复杂一些，IEEE定义了四种不同的舍入方式，默认的为向偶数舍入（round-to-even）。其他三个分别是向零舍入，向上舍入和向下舍入。

其他三个比较直观，就不再说明，以十进制为例说明“向偶数舍入”，平常的四舍五入中，以舍入到小数点后两位为例，如果第3位小数小于5，则舍去，大于等于5的则进1。向偶数舍入除了最中间的这个值（第3位小数为5）以外，其他与平常的舍入相同，中间的这个值，则要保证在舍入的时候舍入位必须为偶数。比如1.40, 1.60, 1.50, 2.50, -1.50向偶数舍入的结果分别为1, 2, 2, 2, -2

至于为什么要想偶数舍入，这是CSAPP(2e)中的原文：

The problem with such a convention is that one can easily imagine scenarios 
in which rounding a set of data values would then introduce a statistical bias 
into the computation of an average of the values. The average of a set of numbers 
that we rounded by this means would be slightly higher than the average of 
the numbers themselves. Conversely, if we always rounded numbers halfway 
between downward, the average of a set of rounded numbers would be 
slightly lower than the average of the numbers themselves. Rounding toward 
even numbers avoids this statistical bias in most real-life situations. 
It will round upward about 50% of the time and round downward about 50% of the time.

也就是如果在一组数据中，向偶数舍入一般既有向上舍入也有向下舍入，可以一定程度上消除统计平均数时由于总是向上舍入时所带来的统计偏差。

扩展成二进制，就是对形如 XX···X.YY···Y100···二进制模式位的数（最右边的Y是要舍入的位置），根据舍入位是否为偶数来选择是向上舍入还是向下舍入。（至于为什么是100，我还没想明白）

比如10.010, 10.011, 10.110, 11.001向偶数舍入（保留小数点后一位）的结果分别为10.0, 10.1, 11.0, 11.0。