《深入理解计算机系统》练习题2.31答案

柔光的暖阳◎ 2022-04-18 01:36 354阅读 0赞

你的同事对你补码加法溢出条件的分析有些不耐烦了，他给出了一个函数tadd\_ok的实现，如下：

//determin whether arguments can be added without overflow
    //WARNING: THIS code is buggy
    int tadd_ok(int x, int y) { 
        int sum = x+y;
        return (sum-x == y)&& (sum-y == x); }

你看了代码以后笑了，为什么？

# 错误原因 #

这个代码看似可以用来检测int型变量的溢出（如果是两个都是负数，那么可能会负溢出，否则可能正溢出），实际上就算溢出了，这个函数也会返回1。因为这个函数想要的是，如果发生溢出，就返回0。  
所以你会笑==

# 推导 #

**原理**：sum-x与y是恒相等的。

**添加假设**：int型内部是4位二进制。即int型的表示范围为 − 2 w − 1 − 2 w − 1 − 1 -2^\{w-1\} - 2^\{w-1\}-1 −2w−1−2w−1−1。w为4。  
补码形式的各个二进制的权值如下：

**推导**：  
1）如果没有溢出，那么显然sum-x与y相等。

2）如果发生正溢出，那么最终的值为x+y-16。因为正溢出时，算上了第5位二进制的权值 2 4 2^4 24，而int型内部是4位二进制，第5位二进制的权值不应该算上去的，所以就应该减去 2 4 2^4 24，所以最终结果是sum=x+y-16。  
而sum-x = y-16。-16是第5位二进制的权值 − 2 4 -2^4 −24（此时代表为负数），第5位二进制的权值不应该算上去的，这里就会发生负溢出。既然发生了负溢出，就应该加上 2 4 2^4 24。  
所以其实sum-x = y-16 => y-16+16 => y。推导完成。

3）如果发生负溢出，推导过程类似。