这是一张在人人上看到的图片,这正好是无符号整数溢出的典范。分析起来虽然简单,但还是挺有意思的。
先从整数的表示说起。整数可以用无符号和有符号两种不同的编码表示:前者,无符号整数只能表示大于等于0的数,后者可以表示正数、负数或者0。而C/C++语言支持有符号数和无符号数,而Java只支持有符号数。
无符号数
假设一个无符号整数有w位,用位向量x表示一个二进制数。位向量x可以写成[xw-1, xw-2, ··· x0]。我们用函数B2Uw(Binary to Unsigned)来表示二进制到十进制的转换,如下。那么该数可以表示的范围是0~2w-1。
有符号数
有符号数可以用三种编码来表示:原码、反码和补码。它们的共同点是最高有效位是符号位,最高有效位是1则表示负数,是0则表示正数。但它们的最高有效位的权重不一样。
有符号数的补码用函数B2Tw(Binary to Two’s-complement)来表示:
其中最高有效位xw-1称为符号位,权重是-2w-1。有符号数的反码用函数B2Ow(Binary to Ones’complement)来表示:
它与补码的区别在于最高有效位的权重是-(2w-1-1)。有符号数的原码用函数B2Sw(Binary to Sign-Magnitude)来表示:
与前两种表示方式不同,原码最高为有效位的值的取值是-1或1。
原码和反码的表示方法有一个缺陷,就是+0都用[00···0]表示,但-0在原码中用[10···0]表示,在反码中用[11···1]表示。由于补码对负数和零的处理对计算机最为友好,现在的计算机基本都使用补码来表示。
无符号数的溢出
w位的无符号数所能表示的范围是[0,2w-1],超过范围就将产生溢出。若无符号数使用不慎将产生未知的错误。比如无符号数x和y,用表达式x-y>0来判断x是否比y大,当x比y小时将产生错误的结果。当然这个例子的错误是显而易见的,然而若无符号数使用不当,还会产生不容易的发现错误,例如从有符号数到无符号数的隐式强制转换。
有符号数的溢出
w位的有符号数所能表示的范围是[-2w-1,2w-1-1]。当有符号数的运算结果大于2w-1-1时,将产生正溢出,小于-2w-1时将产生负溢出。
再在来说说最上面那张图,4294967276,这个数字还挺特殊的。因为231是2147483648,232就是4294967296,和4294967276就差了20。余额是用32位数来存储的,而且是32为无符号数存储的。因为32位有符号数能表示的范围是[-2147483648,2147483647],32位无符号数能表示的范围是[0,4294967295]。所以余额用32位无符号整数来表示,最后两位来表示小数。对于32位无符号数,0-1将发生溢出,并得到的结果4294967295。所以图片上的余额是由于0元之后多扣了0.2元,等价于0-20发生了溢出。所以那哥们应该补交0.2元。以及一卡通设计的BUG该修了。