程序员面试系列——有符号数的溢出

àì夳堔傛蜴生んèń 2022-06-09 13:37 69阅读 0赞

请看这样一道题：

#include <string.h>
    #include <stdio.h>
    
    int main(void)
    {
        signed char a[1000]={
       0};
        for(int i=0; i<1000; ++i)
            a[i] = -1 - i;
    
        printf("%lu\n",strlen(a));
        return 0;
    }

请问此程序输出什么？

答案是：255

如果你不信的话，可以亲测。我在ubuntu 64位机上用gcc编译：

> gcc -std=c99 test.c

结果是

> 255

下面我们来分析一下，为什么是这个结果。  
人工计算一下，  
a\[0\] = -1  
a\[1\] = -2  
a\[2\] = -3  
a\[3\] = -4  
…  
a\[127\] = -128

一般来说，有符号数在机器中以补码表示。所以，`signed char`类型可以表示的范围是`-128`到`+127`。

a\[128\] 本应该是`-129`,但是`-129`超出范围了！

那a\[128\]到底是多少呢？

我认为，`-129`可以理解为`-128`减去`1`，进一步理解为`-128`（补码表示为1000 0000）加上`-1`（补码表示为1111 1111），我们可以用二进制计算一下。

![这里写图片描述][SouthEast]

如上图所示，因为位宽只有8位，所以进位被丢弃，结果就是0111 1111，写成十进制就是`127`. 于是，我们可以继续往下算，

a\[0\] = -1  
a\[1\] = -2  
a\[2\] = -3  
a\[3\] = -4  
…  
a\[127\] = -128  
a\[128\] = 127  
a\[129\] = 126  
a\[130\] = 125  
…  
a\[253\] = 2  
a\[254\] = 1  
a\[255\] = 0  
a\[256\] = -1  
…

可以观察出，a\[0\]的值为`-1`,后面的值依次在前一个值的基础上减1，当a\[127\]的值为`-128`的时候，再减去1就成了`127`.

也就是说，`signed char`类型可以表示的范围是`-128`到`+127`。在最小值`-128`的基础上减1，就会向下溢出，回到最大值`+127`。反之，在`+127`的基础上加1，就会向上溢出，回到最小值`-128`。

用数轴来表示就是数轴的最右端（`+127`）和最左端`-128`连在一起了，构成了一个回路。

![这里写图片描述][SouthEast 1]

好的，我们回到正题，按照上面的分析，a\[0\]~a\[254\]的值都不为0，而a\[255\]的值为0，strlen函数是计算字符串长度的，注意，不包括字符串最后的`\0`（其ASCII码的值为0），所以答案就是255.

--------------------

【参考资料】  
\[1\] C语言深度解剖（第二版）（北京航空航天大学出版社）P13  
\[2\] 深入理解计算机系统 （机械工业出版社）

[SouthEast]: /images/20220609/ca30c30ff81a448094153d84c6ae438a.png
[SouthEast 1]: /images/20220609/7bd4f1f0554a475d8797ffd126b5dfc7.png