黑马程序员技术交流社区

标题: 补码加法的证明 [打印本页]

---

作者: 晗修    时间: 2015-6-2 22:29
标题: 补码加法的证明
int a，b，c；
其中a>=0,b<0,c<0;
a,b,c表示为n位2进制数（包括符号位）。  b+c>=-2^n //也就是 这三个数的计算结果不会溢出
a的补码的值就等于a。
b，c的补码的值等于2^n+b//注意 这里不是指真值而是指补码本身代表的二进制数的值
计算过程：
假设|b|=k[n-2]*2^(n-2)+.....+k1*2^1+k0*2^0  ——(n-1)项，符号位为1
～b  按位取反其实就是求1-k(i)的过程
补的值= 1*2^(n-1)        //符号位
                  +(1-k[n-2])*2^(n-2)+...+(1-k1)*2^1+(1-k0)*2^0     // 按位取反
                  +1       //加1
               = 1*2^(n-1) +1*2^(n-2)+...+1*2^0    -    (k[n-2]*2^(n-2)+...++k1*2^1+k0*2^0) +1
               =2^n-1 -|b|+ 1
               =2^n-|b|
               = 2^n+b         
然后是运算
非负数的加法 肯定没有疑问
1:非负数和负数的加法运算
（[a]补+补）的值= a+2^n+b=（a+b）+2^n ////只是代数运算 没有考虑可能存在的要舍去的溢出位（取模）
假设 a +b >=0
那么(a+b)+2^n 在存储为2进制时 首位的1 因为溢出而被丢弃了  
即((a+b)+2^n)%（2^n） = a+b   
则[a]补+补的值 = a+b
[a+b]补 =a+b =[a]补+补 //a+b>0
假设a+b <0
则b<=a+b+2^n<2^n  必定可以表示为n位二进制数
那么[a+b]补 = 2^n+a+b = [a]补+补
因此
无论a+b>=0 或者 a+b <0  [a+b]补 = [a]补+补 均成立

[b+c]补= 2^n+b+c

（补+[c]补）的值= 2^n+(2^n+b+c)     //只是代数运算 没有考虑可能存在的要舍去的溢出位（取模）
因为b+c>=-2^n(否则计算结果本身就溢出而无法存储 无意义的讨论)
那么2^n>2^n +b +c>=0
所以(2^n+(2^n+b+c))%(2^n)=2^n+b+c
则 [b+c]补= 补+[c]补


综上 无论x，y为正负或者0 ，总有 [x+y]补 = [x]补+[y]补这就是为什么计算机内部用补码计算——符号位不需要做其他判断能直接进行加法运算且结果正确。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2