关于   小悟志   网站地图   归档   友情链接   联系   Feed

   云上小悟  +  

当前位置 : 首页 » InfoTech » 补码,模运算和溢出 正文

补码,模运算和溢出

2017年5月22日 / 36次阅读  InfoTech
标签:计算机

拍拍贷

文章《补码,模运算和溢出》的特色图片

在现代计算机中,补码主要用来表示整数(数值整数),CPU在补码的基础上实现加法运算,减法也通过加法来实现(Intel x86的CPU中,都有加法器和乘法器,用加法器实现减法,用乘法器实现除法;当然,某些高级CPU还可能会有更先进的计算部件,一个指令直接进行\(\sin\)和\(\cos\)等计算)。本文总结补码相关知识。

 

先说说模运算(mod):

模可以理解为一个正数,一个上界。在模运算系统中,若A,B,M满足这个关系:\(A=B+K \times M\),K为整数,则记为:\(A \equiv B \pmod M\)。即A,B各除以M后的余数相同,故称B和A为模M同余。也就是说在一个模运算系统中,一个数与它除以模后得到的余数是等价的(这里没有考虑负数)。时钟系统,就是最典型的模运算系统,模是12或24。

 

补码跟模运算啥关系:

假设现在钟表时间是10点,要将它拨到6点,有两种拨法:

1, 倒拨4个小时;

2, 顺拨8个小时;

所以,在模12系统中,\(10-4 \pmod {12} \equiv 10+8 \pmod {12}\)

上式也可以写为:\(-4 \equiv 8 \pmod {12}\)

于是,我们可以说,8是-4对模12的补码。

结论:对于某一个确定的模,某数A减去小于模的另一个数B,可以用A加上(-B)的补码来代替!

这就是为什么补码可以借助加法运算实现减法运算的道理。

 

补码的定义

1, 正数的补码就是它本身;

2, 负数的补码等于模与该负数绝对值之差。

(如果计算之后还是负数,继续迭代,比如:\(-7 \pmod 3 \equiv 2\))

因此,某一个数的补码,不管它是正是负,其补码都是正数!

在计算机中,一般情况下,一个整数由\(n=32\)bit位来表示,正好有符号整数在现代计算机中基本都使用补码来表示。对于有符号的整数,第一位是符号位,那么,有符号整数的模就是\(2^n\)。(n-1个bit的有效数据,模就是2的n次方)

我们定义:

1, 对于n为有符号整数定点整数(小数点在最右边),补码为:

\([X_T]_{补}=(X_T+2^n) \pmod {2^n}\)

\((-2^n \le X_T \lt 2^n)\)

2, 定点小数(小数点在最左边),补码为:

\([X_T]_{补}=(X_T+2) \pmod {2}\)

\((-1 \le X_T \lt 1)\)

从上面定义可以很容易的看出,有效位全0时的补码表示的是负的最小值,因此对于8bit的有符号数,表示范围是-128到127.

补码0的表示是唯一的,机器数表示,不管是定点整数,还是定点小数,都是全0。这样带来了两个好处:

1, 0的表示唯一,减少了+0和-0之间的转换;

2, 少占用一个编码表示,使补码比原码能多表示一个最小负数。

 

补码的计算

可以通过定义证明补码在计算机中的计算规则:对于正数,符号位是0,补码就是其本身,无需计算;对于负数,符号位保持1,其余各位由真值的数值部分“各位取反,末尾加1”得到。

计算机来做取反很easy,再加上1,就能的负数的补码,因此,可以很容易地将减法转换成加法运算。(如果用原码表示负数,计算过程就会复杂许多)

反过来看看,如果从补码来反算出真值

对于正数,补码的数值部分不做改变,跟原码一样,直接就能得到真值;

对于负数,将计算补码的过程反过来,将补码数值部分减1,然后再各位取反,符号位保持1。

再看看如何从\([X_T]_{补}\)求出\([-X_T]_{补}\):

还是“各位取反,末尾加1”,但是这次要连通符号位一起取反。

需要注意的是:最小负数取负后的补码表示是不存在的,如果对最小负数取负数,结果会溢出。

 

关于溢出(overflow)

确定位数的两个数的计算结果,有可能无法在同样的位数范围内表示出来,这时就发生了溢出。溢出的发生是因为产生了进位,而计算机由于存储限制,进位会被丢弃。

有的时候,这种丢弃是允许的,比如两个相同符号数相减,或者两个异号数相加。这时的溢出,恰好就是模运算,最后得到的结果正确。前面说到,如果对最小负数取负,结果会溢出,机器数的结果是没有变化。程序员需要特别注意。

有的计算机采用一种双符号位的补码表示,成为变形补码,也称为模4补码。在这种补码系统中,左符号是真正的符号位,右符号用来判别溢出。

 

无符号编码

有符号整数在计算机内,使用补码表示,因为这样减法和转换成加法,加快CPU的计算;

无符号整数在计算机内,有一种说法,使用无符号编码表示,其实就是原码表示,简单直接。

C语言中,要特别注意有符号数和无符号数混合运算的情况,系统会默认将有符号数也当成无符号数来对待,计算结果也是无符号数。

无符号编码在计算时,也会有溢出。

本文链接:http://www.maixj.net/ict/buma-moyunsuan-yichu-15391
云上小悟 麦新杰(QQ:1093023102)

-- (*^-^*) --

相关文章

评论是美德

无力满足评论实名制,评论对非实名注册用户关闭,有事QQ:1093023102.


前一篇:
后一篇:

栏目精选


©Copyright 麦新杰 Since 2014 云上小悟独立博客版权所有 备案号苏ICP备14045477号-1

网站二维码
拍拍贷
go to top