在计算机中，一个数据类型可以存储数值的容量并不是无限的，它能存储的数值容量是由数据类型占用的比特位数量决定的。此时会有两种情况需要考虑，一是非常大的整数（所有数据类型都容不下了）应该如何去计算，二是超出类型A容量的整数存入类型A后会发生什么变化。为了分析并解决着两类问题，我们首先需要先了解一下计算机中整数是如何存储的。整数是信息的一种表现形式，计算机为了表达信息就需要创造出一种语言，语言由符号组成（比如a-z，汉字等等），由于计算机由物理介质组成，想要使用英文字母进行通信就需要找到具有26种状态的物理介质，显然具有这样性质的物理介质并不容易找到。但是具有2种状态的物理介质就非常容易搞定（比如电路的高低电平），因此计算机采用二进制计数法中作为语言表达信息（计算机中经常可以看到16进制的身影，是因为16是2的4倍，4个二进制数等于1个十六进制数）。想要表达正整数，二进制计数法就足以表达意思了，但它表达负整数就不行了。可以先这样，将最高的比特位作为标志位标记正负，0xxx代表正数，1xxx代表负数，这样问题不就解决了吗。那我们接下来再从运算角度上看看。原码并没有给正数和负数间建立数学联系，因此原码表示的负数参与进计算时出现错误是一种必然。对于人类来讲，通过符号-在逻辑上区分正负数并不是问题，但对于计算机来讲，就比较困难了。我们知道x−yx - yx−y可以看作是x+(−y)x + (-y)x+(−y)，正数y的加法逆元是-y，此时我们将减法运算转换成了加法运算，那么加法逆元能不能使用正数进行表示呢？首先我们已经知道了数据类型存储的数值数量是有上限的，一个数值超出最大值后会出现什么情况呢？答案其实很简单，把多余的部分扔掉就好了，就好比你有一个桶，满了就把水倒掉，留下空桶再继续接水，这个过程可以被称作是模运算（容量被称作是模，模运算和取余的差别在于，取模是向无穷小取整，而取余则向0取整）。因此我们可以找到数值A（≤最大值）对应的数值B（＞最大值），使得数值B参与计算时可以起到和数值A一样的效果（水桶容量为5升，接3升水和接8升水，水桶中最后装的都是3升水，8升水中多出去的5升被倒掉了）。对于12和4它们相加和是2^424（模2^323的整数倍），且根据模2^323进行模运算结果也是相同的，从数学上讲，具备这一类性质的数值属于同余类。假如将正数A看作向前进，那么对应的负数-A就相当于向后退，那么只有向后退才可以达到负数想要的效果吗？当然不是，加上一个大于等于最大值的数值也可以。观察上方的示例推断出，由于模的限制，在计算机中减法与加法运算结果是同余类，由此可以实现减法运算向加法运算的转变，因为加数可以是0，所以作为被加数的加法逆元，其负数表示和正数也是同余类，由此我们可以得到加法逆元的负数表示向正数表示转变的表达式−x≡M−x(modM)-x ≡ M - x (mod M)−x≡M−x(modM)。在计算机中，数据类型占用n个比特位，我是用n2^n2n作为模合情合理吧，那么正数继续沿用原码的表示方式，我们可以非常容易的得到负数的表示方式−x≡n−x(modn)-x ≡ 2^n - x (mod 2^n)−x≡2n−x(mod2n)。由于计算机采用二进制表达信息，所以这里会产生一个非常有意思的事情，就是n2^n2n的二进制表示格式为b1000...000，模n2^n2n下最大值的二进制表示形式为b111...111，即n−2^n -12n−1，因此2^n减去任意数值，都相当于被减数的二进制表示取反后再加1。我们将以n−2^n -12n−1为模的计算方式称作反码。在现在的计算机中，一般使用的都是补码，而不使用反码则是因为它存在较为致命的缺陷。从上方的示例中可以看到，反码表示的正数和负数中同时存在着正零值和负零值，它破坏了数值的连续性和一致性，为了规避此问题采用补码。二进制表示的数值进行模运算，只需要根据模大小将多余的高比特位抹除就可以，这个结论对吗？答案是肯定的，下方会给出推到过程。∑i=w−i(modn)=(w−+⋯+)(modn)=w−(modn)+⋯+(modn)=(w−−n)+⋯+(n−n)+⋯+(−n)=(w−−w−)+⋯+∑i=ni=++⋯+∑i=ni=∑i=ni\sum_{i=0}^{w-1}{x_i2^i\,\,\left( mod\,\,2^n \right)}
=\sum_{i=0}^n{x_i2^i}∑i=0w−1xi2i(mod2n)=(xw−12w−1+⋯+x020)(mod2n)=xw−12w−1(mod2n)+⋯+x020(mod2n)=(xw−12w−1−2n2nxw−12w−1)+⋯+(xn2n−2n2nxn2n)+⋯+(x020−2n2nx020)=(xw−12w−1−xw−12w−1)+⋯+∑i=0nxi2i=0++⋯+∑i=0nxi2i=∑i=0nxi2i从上面的推到中可以看出，低比特位区域的因为数值大小没有超过模所以不受影响，高比特位区域的数值自己和自己消除了，所以上方提出的结论是正确的。计算机为了减法运算而单独实现电路是非常不明智的，考虑到加法逆元可以将减法运算转变为加法运算，所以计算机使用加法运算代替减法运算。在模运算中加法逆元的负数表示可以转变为正数表示（互为同余类），此时负数就被彻底消除。对于计算机来讲，占据n个比特位的数据类型参与加减法运算时，它们结果天生就是模n2^n2n下的同余类计算，因此补码就此产生并成为主流。反码从二进制的角度上观察是比较有趣的（正数取反就可以），但是反码产生的数值会有不连续和不一致的问题，这样的问题应该尽量避免，所以弃用了反码。让整数数据类型A发生异常情况其实都可以归咎为一类，就是数据类型A被塞入了超量整数B，导致整数B进行模运算后再交给数据类型A，使数据类型A中存储的数值与数值B不相符。在C语言中存在着两大类整数数据类型，一是无符号类型，二是有符号类型，两者的区别在于无符号类型只表示正整数，有符号类型既可以表示正整数也可以表示负整数。其中无符号数溢出时，直接对数值取模获得可以获得新的结果。有符号数溢出时，情况会复杂一些，因为有符号数据类型虽然占用了n个比特位，但是它相当于将空间劈开了一半，正整数和负整数各占n−2^{n - 1}2n−1，当数值溢出时，会导致最高比特位（符号位）发生变化。在AMD64架构的机器中，有符号数据类型产生溢出时会被eflags标志寄存器中的OF标志位记录，无符号数据类型产生溢出时会被eflags标志寄存器中的CF标志位记录。由于无符号数据类型产生溢出时不会导致符号改变，所以一般会将这种情况称作是回绕。当宽度（占用比特位数量）更小的数据类型向宽度更大的数据类型进行转换时，不会带来什么问题，仍会保留原数值，但反之则不然。宽度更大的数据类型向宽度更小的数据类型进行转换时，一是原数值在进行模运算后后可能出现数值上损失，二是符号位可能会发生变化，三是目标数据类型可能与源数据类型对符号位的解释不一致导致产生的数值变化。一个变量在程序的作用大致可以分成对外输出和作为限制条件存在两种，当我们可以控制变量时，就可以突破原有的
...(已截断)
---
来源: 看雪论坛
原文链接: https://bbs.kanxue.com/thread-284160.htm
PWN入门-14-整数溢出收徒
416 浏览
2 回复
整数溢出收徒
还收徒不？