算法中的溢出

‘壹’ 补码运算为什么会溢出

什么是溢出？

溢出，是指数据的大小，超出了编码所能表示的范围。

不仅是补码计算，任何形式的计算，都可能产生溢出。

比如：1999 年、2000 年 ...，这是用 4 位十进制表示。

当到了 9999 年，再过一年，你如果还用 4 位表示，就会溢出了。

如果不限制编码的位数，那就不存在溢出的问题。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

两种常用的数字，在计算机中，都是用机器码代表的。其范围如下：

机器码，无论代表什么数字，只要运算结果超出范围，就是【溢出】。

但是，在计算机专业人的嘴里，就不一样了。

【无符号数的溢出】，不叫溢出，要叫做【进位】。

【带符号数的溢出】，才叫做【溢出】。

搞计算机的这些人，基本概念不清，却自命不凡！

冒充脑回路清奇。。。正常人对此，就只能无语了。

－－－－－－－－－－－－－－－－－－－－－－－－－－－

就按照计算机专业的说法吧：

溢出，是指“补码运算结果超出范围”。

溢出的特征，是“符号错误”。

知道了这些，判断是否溢出，就很容易了。

一、无符号数的运算，肯定不会溢出。只有进位。

二、只有：正＋正、负＋负，才有可能超出范围。不是这些，就绝不会溢出。

三、人工用数值计算。和，如果没有超出范围，就没有溢出。

四、人工用补码计算。和的符号，如果正确，就没有溢出。

五、编个程序，让计算机计算。然后观察溢出标志位，为零，就没有溢出。

六、人工用补码计算，如“最高位的进位”和“次高位的进位”相同，就没有溢出。

第六种，本是 CPU 的硬件所用的方法。

硬件，其理论基础，是很晦涩难懂的。

异或运算，一般也不需要初学者掌握。

但是，一些爱得瑟的老师，偏爱介绍这种方法。

却又拿不出任何的理论！

其实，这是很无聊的表现，其实，他们就是想要难为学生。

‘贰’ 计算机补码运算的溢出叛别方法

使用双符号位进行计算就可以了,正的前面符号位是"00",负的前面的符号位是"11",假如进行补码运算的结果符号位是"00"或者"11",则表示没有溢出;假如结果符号位是"10"或者"01",则表示有溢出.

‘叁’ 什么是下溢和上溢

上溢是当一个超长的数据进入到缓冲区时，超出部分被写入上级缓冲区，下溢是当一个超长的数据进入到缓冲区时，超出部分被写入下级缓冲区。

随便往缓冲区中填东西造成它溢出一般只会出现“分段错误”（Segmentation fault），而不能达到攻击的目的。

最常见的手段是通过制造缓冲区溢出使程序运行一个用户shell，再通过shell执行其它命令。如果该程序有root或者suid执行权限的话，攻击者就获得了一个有root权限的shell，可以对系统进行任意操作了。

攻击原理：

通过往程序的缓冲区写超出其长度的内容，造成缓冲区的溢出，从而破坏程序的堆栈，造成程序崩溃或使程序转而执行其它指令，以达到攻击的目的。造成缓冲区溢出的原因是程序中没有仔细检查用户输入的参数。

当程序需要接收用户数据，程序预先为之分配了4个格子（下图1中黄色的0~3号格子）。按照程序设计，就是要求用户输入的数据不超过4个。而用户在输入数据时，假设输入了16个数据，而且程序也没有对用户输入数据的多少进行检查。

就往预先分配的格子中存放，这样不仅4个分配的格子被使用了，其后相邻的12个格子中的内容都被新数据覆盖了。这样原来12个格子中的内容就丢失了。

以上内容参考：网络-缓冲区溢出

‘肆’ c语言数据溢出怎么办

C语言的强大之处就在于他的灵活性，程序员自己把握。编译器可以帮助预防错误，但有些程序会利用溢出，所以溢出不完全是错误的事情。
1、溢出：
数据类型超过了计算机字长的界限而出现的数据溢出；
2、溢出可能原因：
当应用程序读取用户数据，复制到应用程序开辟的内存缓冲区中，却无法保证缓冲区的空间足够时 (假设定义数组int Array[10]， 而在调用时使用Array[11] 或存放的数据超过int类型容量等)， 内存缓冲区就可能会溢出.
3、溢出因素分析：
由于C/C++语言所固有的缺陷，既不检查数组边界，又不检查类型可靠性，且用C/C++语言开发的程序由于目标代码非常接近机器内核，因而能够直接访问内存和寄存器，只要合理编码，C/C++应用程序在执行效率上必然优于其它高级语言。然而，C/C++语言导致内存溢出问题的可能性也要大许多。

‘伍’ 针对定点小数加法运算，分析 产生溢出的原因，并给出两种溢出的方法

（1）产生“溢出”的原因：        
当最高有效数值位的运算进位与符号位的运算进位不一致时，将产生运算“溢出”。 当最高有效位产生进位而符号位无进位时，产生上溢； 当最高有效位无进位而符号位有进位时，产生下溢。 
（2）“溢出”检测方法： 
为了判断“溢出”是否发生,可采用两种检测的方法。
第一种方法：采用双符号位法, 称为“变形补码”或“模4补码”，可使模2补码所能表示的数的范围扩大一倍
第二种溢出检测方法：采用“单符号位法”。当最高有效位产生进位而符号位无进位时，产生上溢； 

‘陆’ 我的程序的出现堆栈溢出，怎么办

虽然我没有亲眼见到你的源程序代码，但是根据你所描述的情况来看，我估计你在你的程序源代码中使用了递归调用子函数。因为程序在频繁地递归调用子函数过程中就会产生频繁地产生压栈、出栈操作。
递归调用子函数的最大优点就是：程序的编写起来较容易、并且程序的可读性较好；但是它也有它的缺点。即：如果需要处理的数据量很大时，就必然会导致堆栈溢出的现象。此时就必须将递归算法修改为非递归的算法。
至于具体的修改方法，现在的数据结构教材上都有讲解的。但是这样一改，其程序的非递归可读性必然不如递归调用的看起来可读性要好。
例如：最最经典的递归调用子函数就是：计算一个整数的阶乘。当需要计算的整数比较小的时候，那么使用递归调用子函数来编写程序，那简直就是一种享受。但是当需要计算的整数很大、很大的时候，那么如果还是使用递归算法，必然会造成堆栈的溢出。此时就必须要把递归算法修改为非递归算法。

‘柒’ 计算机基本运算中，补码运算怎样判断数值是否有溢出

用二进制补码，表示正负数，具有一定的表示范围。

当运算结果，超出了它所能表示的范围，就会溢出。

如果出现了溢出，这组代码，就不能正确表示结果。

八位二进制代码：00000000~11111111。

也就是十进制数：0~255。

它们如果是补码：0~127，就直接代表零和正数；

128~255，则以补码代表－128~－1。

八位补码的范围：－128~＋127。

在127上，再加上＋1，就超出了范围，必然溢出。

这两个正数相加之后，将会得出128，却是个负数。

在－128上，再加上－1，也超范围，也会溢出。

这两个负数相加之后，将会得出127，这是个正数。

补码计算出现了溢出，最重要的特征是：符号不正确。

你只要判断符号正确与否，就可以了。

另外，

能够超出范围的算法，一定是：正＋正、负＋负。

捎带还有：正－负、负－正。

除了这四种算法之外的计算，都不可能溢出。

‘捌’ 二进制补码运算溢出判断

补码运算的溢出判别方式为双高位判别法，利用Cs表示符号位是否进位，利用Cp表示最高数值位是否进位。如果Cs ^ Cp的结果为真，则代表发生了溢出（运算结果大于0则为负溢出，小于0则为正溢出），否则运算结果正确。

例如：

1000 0011（补码为-3，原码为-125） 0000 0011（补码为3，原码为3）

+1100 1001（补码为-73，原码为-55） +1100 1001（补码为-73，原码为-55）

10100 1100（补码为76，原码为76） 01100 1100（补码为-76，原码为-52）

Cs为1，Cp为0所以产生了负溢出。 Cs为0，Cp为0所以结果正确。

(8)算法中的溢出扩展阅读

二进制补码运算规则：

1、正数：原码=反码=补码

2、负数：原码（第一位是1符号位）=反码（除第一位符号位外，其它按位取反）=补码（反码+1）

3、0：原码=反码=补码=0

举例：

1、15-5=15+(-5)=10

原码：

15：0000 1111

-5：1000 0101

反码：

15：0000 1111

-5：1111 1010

补码：

15：0000 1111

-5：1111 1011

‘玖’ 二进制补码如何判断溢出

首先符号相反是不会产生溢出的~~所以就是X0Y0或~X0~Y0X0Y0~S0：负+负仍为负，故S0若0（即为正）则溢出；~X0~Y0S0：正+正仍为正，故S0为1（即为负）则溢出；至于减法似乎不对比如1-（-1）就为00000001-11111111=00000010，结果是对的，没有溢出，所以减法应该是不对的；正确的方法还是应该判断最符号位进位和最高位进位，异或为1则溢出，为0不溢出，加减法都适用。

‘拾’ 快速排序算法运行显示栈溢出，怎么解决

刚运行 QuickSort(array,0,array.length-1);这句的时候，进入函数内部key=11, 然后根据判断条件要找到比key小的数字，但是你的数组为int[]array=new int[]{11,213,134,44,77,78,23,43};没有比11小的，所以循环会直接运行到最后，当退出循环的时候,i变成了8，但是你的数组只有8个元素，对应索引0-7，所以会出现数组越界的情况，楼主应该是编程新手吧，编程强调逻辑能力，要把很多条件综合考虑才可以，否则编写出来的程序会有很多bug。