用计算机组成原理解释出现在C语言程序中的一个问题

2018第一篇博客,good lucky~~~

0x000 遇到的问题

写这篇博客的缘由是上次刷OJ时,碰到的一个问题.

在太平洋的一个小岛上，岛民想要建立一个环岛的堤坝，我们可以将小岛简化为一个二维平面，你需要使用K条边（这些边要么是水平或者垂直长度为1的边，要么是45度倾斜的长度为sqrt(2)的边）围成一个多边形，多边形的顶点必须位于整点，然后要让围成的多边形面积最大，你需要求出最大面积是多少。

推出递推公式后,在奇数条件下需要减去一个0.5,当n足够大时,我发现用答案去减这个0.5后答案不会变,用了各种方法都没有能够让答案变化0.5.虽然最后用JAVA解决了此题,但是这个问题一直没有得到解决.

0x001 发现曙光

最近这些天在复习计算机组成原理,在看到数据的表示与运算这一章的时候,发现浮点数的四则运算是通过对阶，让小的数字通过右移操作与大的数字的阶码相同，然后通过尾数相加所得。
我便有了一个猜想,是不是因为数字的阶码相差过大而导致0.5通过位移操作而变为了0?

0x010 推导

上图是IEEE 754的标准,我们可以看到在计算机中64位浮点数的数符单独占1位,阶符和阶码占11位,尾数占52位,而尾数的第一位是隐藏位.
在IEEE 754中,对于0.5,其符号位为0,指数(阶符和阶码部分)为-1,规格化后的尾数为1.0,在IEEE 754中的尾数为M = 1000 ... 0000(加上隐藏位共53位,以原码进行表示).
故猜想:当其与一个阶码为52的数字相加时,由小阶向大阶看齐的规则,M向右移动53位之后变成了0000 ... 0000(共53位).
2^52 = 1000 0000 ... 0000(共53位)
1000 0000 ... 0000 + 0000 0000 ... 0000 = 1000 0000 ... 0000
故猜想当数字达到2^52时,加上0.5不会改变其值.

0x011 通过二分法进行验证

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
LL MAX_LL =  9223372036854775000;
double eps = 1e-8;
LL seek(){
    LL l = 1,r = MAX_LL;
    while(l<r){
        LL mid = (l+r)>>1;
        double right = mid+1,left = mid-1;
        double right1 = right-0.5,left1= left+0.5;
        if(fabs(right-right1)<eps&&fabs(left-left1)>eps){
            return mid;
        }else if(fabs(right-right1)<eps&&fabs(left-left1)<eps){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
}
int main()
{
    LL ans = seek();
    cout<<ans;
    return 0;
}

运行结果为4503599627370496

证明我们的猜想是正确的.

0x100 未解决的一个小细节

通过推导我们证明了2^52加上0.5不会改变其值.但是在测试中,当取值属于[2^52+1,2^52+10)时,每次加上0.5或者减去0.5之后的答案会多1或者少1,而不是上面所说的不变.我猜测是由于0.5进行右移的时候当1被移掉时应用了0舍1进的方式,在这段区间内产生了多1或者少1的现象,当然也有可能是C语言内部的问题,除此细节外,其余的大于2^52的数都与我的猜想一致.
1
2
3
4
5
6
int main()
{
LL A = 4503599627370496+1;
printf("%.1lf %.1lf\n",A-0.5,A+0.5);
return 0;
}

4503599627370496.0 4503599627370498.0

0x101 后记&参考

第一次用硬件知识解释软件中遇到的问题,收获颇多.
《计算机组成原理》作为计算机专业唯一一本关于硬件的书,非常值得去学习,不然我们只会把在软件中碰到的问题归结与玄学之流.这显然是不符合理工科的探索精神的.
IEEE754浮点数的表示方法