定点数的表示与运算

定点数编码

Tips:对于分式的定点数表示的小技巧.
x = 5/8,可以看作:

  • 5 = 00101 右移(小数点左移) 3 = log(8) = log(2^3) ,从而得到x = .10100
    (假设机器字长是5)

注意,此处的右移并不是下面将要介绍的各种移位,而是我们通常使用的移动。
例如15.7=157/10就是将 157. 的小数点左移一位。

原码表示法

[x]={x2n>x02nx=2n+x0x>2n[x]_{\text原}=\begin{cases}x&2^n\gt x\geq 0\\ 2^n-x=2^n+|x|&0\geq x \gt -2^n \end{cases}

其中,[x][x]_{\text 原}是原码的机器数,xx是真值,n=0,1,2,...n=0,1,2,...
即,当x>0x\gt0 时,原码就是其本身的二进制数,否则最高位置 1 ,其余不变。

注:真值为零的原码表示有正负两种,即[0]=00000[-0]_{\text 原}=\mathbf 0 0000[+0]=10000[+0]_{\text 原}=\mathbf 1 0000

补码表示法

显然,对于原码表示,想要对数据进行加减运算是十分繁琐的,因此引入补码表示来解决这个问题,不仅如此,通过补码表示,数据的加减都能转换为纯加法计算。

  • 纯小数补码定义:

[x]={x1>x02+x=2x0x>1(mod2)[x]_{\text补}=\begin{cases}x&1\gt x\geq 0\\ 2+x=2-|x|&0\geq x \gt -1 \end{cases}(\mod 2)

  • 纯整数补码定义:

[x]={0,x2n>x02n+1+x=2n+1x0x>2n(mod2n+1)[x]_{\text补}=\begin{cases}0,x&2^n\gt x\geq 0\\ 2^{n+1}+x=2^{n+1}-|x|&0\geq x \gt -2^n \end{cases}(\mod 2^{n+1})

其中,“0,x0,x”表示在真值xx前补0

当字长为n+1n+1时,整数补码能表示的范围是:2nx2n1-2^n\leq x \leq 2^n-1,比原码多了一个2n-2^n.

原因是补码中零的表示是唯一的,下面以字长为5进行示例
显然有[0]=[+0]=00000[-0]_{\text 补}=[+0]_{\text 补}=\mathbf 0 0000
[+0]=10000[+0]_{\text 原}=\mathbf 1 0000 中的10000\mathbf 1 0000 在补码中用来表示2n-2^n.

  • 变形补码

[x]={x1>x04+x=4x0x>1(mod4)[x]_{\text补}=\begin{cases}x&1\gt x\geq 0\\ 4+x=4-|x|&0\geq x \gt -1 \end{cases}(\mod 4)

变形补码又称 模4补码。上面给出的是 双符号位的补码小数定义。
其中,"00"表示正,"11"表示负,一般用在完成算术运算的ALU部件中。

  • 模4补码具有模2补码的全部优点,且更容易检查加减运算中出现的溢出问题(这将在下面继续阐述)。
  • 值得注意的是,模4补码仅需一个符号位,因为任意一个正确的数值其模4补码的两个符号位一定相同。
  • 只有在把模4补码的数送往ALU进行加减运算时,才把符号位送到ALU的双符号位中,即 只在ALU中才采用双符号位
补码的由来

想象现实中的时钟.

假如一个时钟比实际时间快了2小时指向10点,那么为了让它回到正确的时间点,即8点,我们需要人为地将指针往回拨2小时,即实现Times时钟Times时钟2Times_{\text{时钟}}\leftarrow Times_{\text{时钟}}-2

那么如果这个时钟的指针只能顺时针走怎么办呢?
事实上,我们可以将指针按顺时针一直拨到下一个循环的8点(即20点)。也就是说,实现:
Times时钟Times时钟+122Times_{\text{时钟}} \leftarrow Times_{\text{时钟}}+12-2

显然,其中的12就是一个时钟的周期。

同样的思想可以引入到二进制当中,我们知道一个字长固定的机器码,在累加有限长的数值之后会陷入“循环”。例如8字长的机器码 11111111,加1之后就变成了 00000000.
也就是说,该机器码的“周期”是282^8

因此,如果我们要“往回拨00000001”,即表示 -00000001,也可以用类似的方法。

00000001=2800000001=(11111111+00000001)00000001=(1111111100000001)+00000001)=11111110+00000001=11111111\begin{aligned}-00000001=2^8-00000001&=(11111111+00000001)-00000001\\&=(11111111-00000001)+00000001)\\&=11111110+00000001\\&=11111111\end{aligned}

上式中的等号并不是数值上的相等,仅作推导用。
值得注意的是,推导中倒数第二步的11111110就是00000001按位取反得到的。

虽然前面强调了等号不是数值相等,但是因为机器码的性质我们可以直接运用在计算中。即可以利用这种表示方法,以加法的方式计算减法
记a,b均为正数,则有:

(ab)mod2n=[(ab)+2n]mod2n=[a+(2nb)]mod2n=(a+b)mod2n\begin{aligned}&(a-b)\mod 2^n\\=&[(a-b)+2^n]\mod 2^n\\=&[a+(2^n-b)]\mod2^n\\=&(a+b_\text 补)\mod2^n\end{aligned}

原补码转换

根据以上定义,可以轻易得出,对于正数的表示,补码和原码是一致的。
而对于负数,其转换方法为: 符号位不变,数值部分按位取反,末位+1
原码转补码补码转原码都利用此方法,原因是补码的补码就是原码

此外还有,B的补码转负B的补码方法:包括符号位在内,全部按位取反,末位+1

在上述转换中,出现了“按位取反”的步骤,其实将原码除符号位取反的这个中间步骤出现的编码就是 反码,由于反码在计算机中不常用,仅作为中间步骤,这里不再赘述。

移码表示法

移码常用来表示浮点数的阶码。只能用来表示整数。

移码的定义如下:

[x]=2n+x(2n>x2n)[x]_{\text 移}=2^n+x\quad(2^n \gt x \geq -2^n)

其中,n+1n+1是机器字长.

移码具有如下几个特点:

  1. 零的表示唯一
  2. 补码符号位取反就能得到移码
  3. 移码大小与真值大小对应,移码越大,真值就越大,反之亦然
  4. 移码全0时,对应真值最小值2n-2^n,移码全1时,对应真值最大值2n12^n-1

运算方法与电路

ALU中,运算器包括有加减乘除的四则运算,与或非异或等的逻辑运算,还有移位、求补等操作功能。
而ALU的核心部件则是 (并行)加法器

在设计多位加法器时,为了加快运算速度而采用了快速进位链,即对加法器的每位都生成两个信号:

  • 进位信号g=XiYig=X_iY_i
  • 进位传递信号p=XiYip=X_i\oplus Y_i

串行进位的并行加法器中,影响加法器运算速度的因素有:

  • 门电路的级延迟
  • 元器件的速度
  • 进位传递延迟(最主要
  • 各位加法器的速度不同

移位操作

  • 算术移位:保留符号位
码制填补代码
正数原码、补码、反码0
负数原码0
反码1
补码左移补0
右移补1

补码左移的前提条件是其原最高有效位原符号位相同,否则会发生溢出

  • 逻辑移位:将操作数视为无符号数,补0
  • 循环移位:通过是否带 进位标志位CF 进行分类
    四种循环移位示意

加减运算

在前面的描述中依然阐明了补码对于加减法的便利,此处给出直观了当的公式:

let[A]=X,[B]=Y,then[A+B]=[A]+[B]=X+Y(mod2n+1)[AB]=[A]+[B]=X+(Y+1)(mod2n+1)\begin{aligned} \text{let}\quad [A]_{\text 补} &= X,[B]_{\text 补} = Y,\text{then}\\\\ [A+B]_{\text 补} &= [A]_{\text 补}+[B]_{\text 补} = X+Y\quad(\mod2^{n+1})\\ [A-B]_{\text 补} &= [A]_{\text 补}+[-B]_{\text 补} = X+(\overline Y+1)\quad(\mod2^{n+1}) \end{aligned}

公式的定点小数证明
  • 补码加减运算电路

补码加减运算部件
上图的加法器是带标志的加法器。显然本电路能够同时胜任无符号和有符号的整数加减运算。

对于带符号的整数x,yx,y,假设其补码分别为X,YX,Y,其运算结果由上图所示的电路产生。其中,Sub\text{Sub}信号表示是做加法还是做减法,取1表示减法。

并且,由于[Y]=Y+1[-Y]_\text 补 = \overline Y + 1,而电路中仅仅出现了Y\overline Y,所以,其实这里的Sub\text{Sub}也是 低位进位输入信息

  • 零标志ZF=1\text{ZF}=1,表示结果为0溢出
  • 溢出标志OF=1\text{OF}=1,表示运算结果溢出(只对有符号数的运算有意义)
  • 符号标志SF\text{SF},表示结果的符号,也即是结果的最高位(只对有符号数的运算有意义)
  • 进/借位标志CF\text{CF},表示无符号数运算时的进/借位情况,用以判断是否溢出。CF=SubCout\text{CF}=\text{Sub}\oplus C_{out}. 即加法时,Cout=1C_{out}=1表示溢出,减法时Cout=0C_{out}=0表示溢出(只对无符号数的运算有意义)

溢出判别

对于补码来说,当两个正(负)数相加得到的结果为负(正);当一个负数减去一个正数得到的结果为正时,说明计算出现了溢出

补码定点数的加减运算溢出判断拥有3个方法:

  1. 一位符号位:当两个操作数A,BA,B的符号As,BsA_s,B_s相同,但是与运算结果的符号SsS_s不同时,表明结果溢出。记溢出信号VV,且当V=1V=1表示溢出,则有VV的逻辑表达式:V=AsBsSs+AsBsSsV=A_sB_s\overline S_s+\overline{A_sB_s}S_s.

  2. 双符号位:即前面所说的 模4补码/变形补码的运用。运算结果拥有两个符号位Ss1,Ss2S_{s1},S_{s2},逻辑表达式为V=Ss1Ss2V=S_{s1}\oplus S_{s2}.此外,有:

    • Ss1Ss2=00S_{s1}S_{s2}=00,结果为正,无溢出;
    • Ss1Ss2=01S_{s1}S_{s2}=01,结果正溢出;
    • Ss1Ss2=10S_{s1}S_{s2}=10,结果负溢出;
    • Ss1Ss2=11S_{s1}S_{s2}=11,结果为负,无溢出.
  3. 一位符号位+进位情况判断:当符号位的进位CsC_s与最高数位的进位C1C_1不同时,说明溢出,即V=CsC1V=C_s \oplus C_1

♾️做题技巧:已知十进制数或者容易求出十进制数时,我们可以直接将其十进制数进行运算,通过判断十进制运算结果是否在对应字长所能表达的范围内来判断是否溢出

乘法运算

回忆算术中,列竖式计算乘法的过程(此处假设 满2进1):

0.1011×0.11010.1011 ⁣ ⁣ ⁣0.0000 ⁣ ⁣ ⁣ ⁣ ⁣ ⁣0.1011 ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣0.1011 ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣0.0000 ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣0.10001111\begin{aligned} &0.1011\\ \times &0.1101\\ \hline &0.1011\\ &\!\!\! 0.0000\\ &\!\!\!\!\!\! 0.1011\\ &\!\!\!\!\!\!\!\!\! 0.1011\\ &\!\!\!\!\!\!\!\!\!\!\!\! 0.0000\\ \hline&\!\!\!\!\!\!\!\!\!\!\!\!0.10001111 \end{aligned}

可以发现,我们是按照乘数从低位到高位的数值进行判断,从而累计求和,期间还需要将“加数”进行左移操作的一系列步骤进行乘法运算的。
类似地,我们可以反过来通过按照乘数从低位到高位,此外伴随着部分积(即计算过程中我们一直在累加的中间变量)进行右移操作来得到同样的结果。

于是就衍生出了如下算法……

原码一位乘法

[x]=xs.x1x2xn,[y]=ys.y1y2yn[x]_{\text 原}=x_s.x_1x_2\dots x_n,[y]_{\text 原}=y_s.y_1y_2\dots y_n.则:

先对符号位进行运算xsysx_s\oplus y_s,然后将x,yx,y剩下的二进制码作为无符号数进行处理。

记部分积为AnsAns,长度与被乘数一致为n+1n+1。从yny_n开始,初始化Ans=0Ans=0,然后依次循环执行:

  1. AnsAns+yixAns\leftarrow Ans+y_i|x|;
  2. AnsSARAns \quad\text{SAR}
  3. 重复1和2直到y1y_1结束(一共n次)

其中,SAR(逻辑右移):shift arithmetic right

考虑到运算时可能出现绝对值大于1的情况,因此部分积和被乘数都取 双符号位

下面给出一个示例:设机器字长为5位,其中一位是符号位。且x=0.1101,y=+0.1011x=-0.1101,y=+0.1011,利用原码一位乘法求P=xyP=x·y.
原码一位乘法示例

补码一位乘法Booth 算法)

下面先简要阐述Booth算法的基本流程:

[x]=xs.x1x2xn,[y]=ys.y1y2yn[x]_{\text 补}=x_s.x_1x_2\dots x_n,[y]_{\text 补}=y_s.y_1y_2\dots y_n,将符号位参与计算,运算数以补码表示且被乘数与部分积都取双符号位。

  1. 记部分积初值Ans=0Ans=0
  2. 乘数末位增加附加位yn+1y_{n+1},初值置1
  3. 根据(yn,yn+1)(y_n,y_{n+1})的取值,按下表执行
yny_nyn+1y_{n+1}操作
00Ans  SARAns\;SAR
01AnsAns+[X],Ans  SARAns\leftarrow Ans+[X]_{\text 补},Ans\;SAR
10AnsAns+[X],Ans  SARAns\leftarrow Ans+[-X]_{\text 补},Ans\;SAR
11Ans  SARAns\;SAR
  1. 循环执行第3步n+1n+1次,此时得到了n+1n+1次对AnsAns的累加,并且最后一次不右移,此时执行了nn次右移。

下面给出一个示例:设机器字长为5位,其中一位是符号位。且x=0.1101,y=+0.1011x=-0.1101,y=+0.1011,利用Booth算法求P=xyP=x·y.
Booth算法示例

拓展|Booth算法原理

由于乘法计算的本质就是加法的累加,因此当乘数的二进制代码中“含1量”过高时,必然会出现大量频繁的加法计算,但事实上这并不是必要的

回忆小学时,我们曾经做过如下的简便计算:9×99=9×(1001)=9009=8919\times 99=9\times (100-1)=900-9=891
这就是一种化简方法,在二进制中同样有类似的化繁为简的妙用,例如:
001111100=01000010001111100=010000-10. 注意,这里不能看成是用010000减去10,而应该看成二进制的第二位取-1(负1)。

显然如果用010000-10作为乘数的话,比起前者(001111100)机器需要做5次累加来说,计算量减小到了2次。但是第一次是做减法而不是加法,因此对于补码来说才更容易实现。

那么问题又来了,我们该如何“一眼看出”001111100可以化为010000-10呢?

我们记乘数Y=(ys.y1y2yn)2Y=(y_s.y_1y_2\cdots y_n)_2,所以ys=0y_s=0,因此:

Y=y121+y222++yn12(n1)+yn2n2Y=y120+y221+y322++yn2(n1)2YY=Y=y120+(y2y1)21++(ynyn1)2(n1)+(0yn)2n\begin{aligned}Y&=y_12^{-1}+y_22^{-2}+\cdots +y_{n-1}2^{-(n-1)}+y_n2^{-n}\\2Y&=y_12^0+y_22^{-1}+y_32^{-2}+\cdots+y_n2^{-(n-1)}\\2Y-Y=Y&=y_12^0+(y_2-y_1)2^{-1}+\cdots+(y_n-y_{n-1})2^{-(n-1)}+(0-y_n)2^{-n}\end{aligned}

yn+1=ys=0y_{n+1}=y_s=0, 则第一项和最后一项就分别为(ysy1)20,(yn+1yn)2n(y_s-y_1)2^0,(y_{n+1}-y_n)2^{-n}.

由于yi{0,1}y_i\in \{0,1\},所以有:

  1. yi+1=yiy_{i+1}=y_i时,第ii项取0
  2. yi+1>yiy_{i+1}\gt y_i时,第ii项取1
  3. yi+1<yiy_{i+1}\lt y_i时,第ii项取-1

此时我们再来回看 Booth算法的操作步骤表,就显得十分简单了.

yny_nyn+1y_{n+1}操作
00+0,右移一位
01+[x]补,右移一位
10+[-x]补,右移一位
11+0,右移一位

除法运算

回忆算术中,列竖式计算除法的过程:

  0.11010.1101)      0.10110    0.01101   0.010010    0.001101  0.00010100    0.00001101  0.00000111\begin{aligned} & \quad\;0.1101 \\ 0.1101 & \overline{)\;\;\;0.10110\quad\quad } \\ & \underline{-\;\;0.01101\quad}\quad\quad\ \\ & \quad\;0.010010 \\ & \underline{-\;\;0.001101\quad} \\ & \quad\;0.00010100\\ & \underline{-\;\;0.00001101}\\ & \quad\;0.00000111 \end{aligned}

手算除法时,我们是先判断被除数能不能被除数减,如果能则商1,否则商0;然后我们将除数补0右移,再和余数进行比较,如此往复直到余数为0或商达到指定的位数要求。

同样的逻辑,事实上也可以用机器进行实现。

由于机器并不会像人类一样直接判断大小,因此需要先作减法,通过对余数判断正负来决定此时的商。若余数为正,则商1,反之亦然。
此外,当发现余数为负时,为了下一步计算,事实上应该恢复上一次的余数,以便再继续往下运算。而要恢复原来的余数,只要当前的余数加上除数即可,这种方法称为恢复余数法
但由于要恢复余数,使除法进行过程的步数不固定,因此控制比较复杂。实际中常用不恢复余数法,又称加减交替法。其特点是运算过程中如出现不够减,则不必恢复余数,根据余数符号,可以继续往下运算,因此步数固定,控制简单。

原码加减交替除法

设被除数和除数分别为[x]=xs.x1x2xn,[y]=ys.y1y2yn[x]_{\text 原}=x_s.x_1x_2\dots x_n,[y]_{\text 原}=y_s.y_1y_2\dots y_n,将符号位单独计算,显然商的符号Qs=xsysQ_s=x_s\oplus y_s,商的数值Q=x/y|Q|=|x|/|y|.

不恢复余数法的规则如下:

  1. 被除数(余数)减去除数作为此次计算的余数,即xy=x+[y]|x|-|y|=|x|+[-|y|]_{\text 补}
  2. 若余数为正,商上1,然后余数和商都左移一位,再将余数减去除数
  3. 若余数为负,商上0,然后余数和商都左移一位,再将余数加上除数
  4. 重复上述步骤,直到完成运算(重复了n+1n+1次)。若第n+1n+1步得到的余数为负,将其加上y|y|才能得到正确的余数(恢复余数),此时余数和被除数是同号的

下面给出一个示例:设机器字长为5位,其中一位是符号位。且x=0.1011,y=0.1101x=0.1011,y=0.1101,利用原码不恢复余数法求Q=x/yQ=x/y.
加减交替法示例

注意,因为一共左移了4次,所以余数应该是最后得到的余数再乘以242^{-4}

加减交替法的简单证明
  1. 假设第i1i-1次求商所得余数为Ri10R_{i-1}\geq 0,根据算法,本次商上1,然后将余数左移一位,得到2Ri12R_{i-1}
  2. ii次求商,此时余数为Ri=2Ri1yR_i=2R_{i-1}-|y|,则:
  3. Ri0R_i \geq 0,商上1,第i+1i+1次求商时,余数Ri+1=2RiyR_{i+1}=2R_i-|y|
  4. Ri<0R_i \lt 0,商上0,此时余数为负,那么:
    • 如果选择 恢复余数,要将RiR_i加上除数y|y|实现恢复,然后再左移进行下一次计算。
      所以第i+1i+1次求商时,余数Ri+1=2(Ri+y)y=2Ri+yR_{i+1}=2(R_i+|y|)-|y|=2R_i+|y|
    • 如果选择 不恢复余数,而是根据不恢复余数法,直接对余数左移,然后再在i+1i+1次时加上y|y|
      显然,此时的余数Ri+1=2Ri+yR_{i+1}=2R_i+|y|

通过上述推导不难发现,无论是恢复余数还是不恢复余数只做加法,结果都不变。因此加减交替法是切实可行的。
最主要的是,加减交替法固定了机器每一步的操作,所以使得运行上更加可控

补码加减交替法

补码的核心思想与原码是一致的,并且显而易见地,原码的除法实现中也借助了补码来实现运算。与原码除法有区别的是,补码除法还需要解决以下几个问题:

  1. 求商符的确定;
  2. 如何确定上商值和余数值;
  3. 商要如何校正

对于第一个问题其实很好解决。我们规定被除数除数满足0<x<y0<|x|<|y|,则:
在第一步试减时,

  • xxyy同号:因为不够减,即R0R_0yy异号,所以商上0
  • xxyy异号:因为不够减,即R0R_0yy同号,所以商上1
    因此,第一次试减的商结果就为我们确定了商的符号位,即商通过一次试减就自动完成了。

结论就是:同号商1,异号商0


对于第二个问题,先说明一个现象或者说定理:

  1. 当a,b同号时:
    • 如果|a|>|b|,那么,a-b一定与a、b都同号;
    • 如果|a|<|b|,那么,a-b一定与a、b都异号。
  2. 当a,b异号时:
    • a-b一定与a同号与b异号,无法判断|a|和|b|的大小关系。
    • 如果|a|>|b|,那么,a+b一定与a同号与b异号;
    • 如果|a|<|b|,那么,a+b一定与a异号与b同号。

由于加减交替法要求余数不断左移,因此在a做被除数,b做除数时,我们无法根据a的符号进行辨别。因此,我们以除数b的符号作为依据。
即:x,yx,y同号,并且能商1时(即y/x1|y|/|x|\geq 1时),([x]+[y])([x]_\text 补+[-y]_\text 补) 一定与yy 同号,如果异号则只能商0;相反,x,yx,y异号时只有([x]+[y])([x]_\text 补+[y]_\text 补)yy 异号才能商1,否则只能商0.

因为同号和异号的判断依据不同,为了简便计算这里统一为:
余(数)除(数)同号上商1,余除异号上商0

之所以能这样统一,是源于补码的特殊性
这里我们延续第一个问题(商符号的确立)进行简要解释:
因为x,yx,y同号时,商的符号位是0,并且之后的上商计算其实是和原码是一样的;
而在x,yx,y异号时,商的符号位是1,按照上面的统一规则的话,其实我们后面上的商都是反码


对于第三个问题,我们需要回看s上一个问题最终的结论,即异号时是 反码上商.
显然 反码和补码只相差最后1位的确定,并且这1位我们只能估计。而对于小数来说,其实这一位的误差仅仅只是2n2^{-n},因此是可以在一定精度范围内忽略不计的。

目前,补码除法的规则是 商末置1法,即取最后一位为1即可。


阐明了补码除法出现的问题以及如何解决之后,我们得到了补码除法的具体计算步骤。
算法流程如下:

  1. 设被除数和除数分别为[x]=xs.x1x2xn,[y]=ys.y1y2yn[x]_{\text 补}=x_s.x_1x_2\dots x_n,[y]_{\text 补}=y_s.y_1y_2\dots y_n
  2. 符号位参与计算,除数被除数,商和余数均用补码表示。
  3. 如果y=0|y|=0直接结束运算。
  4. x,yx,y同号,则([x]+[y])([x]_\text 补+[-y]_\text 补)作为余数
  5. x,yx,y异号,则([x]+[y])([x]_\text 补+[y]_\text 补)作为余数
  6. 若余数与除数同号,商上1,然后余数和商都左移一位,再将余数减去除数
  7. 若余数与除数异号,商上0,然后余数和商都左移一位,再将余数加上除数
  8. 重复6,7步nn次,商的末位置1

下面给出一个示例:设x=0.1000,y=0.1011x=0.1000,y=-0.1011,利用补码加减交替法求[x/y][x/y]_\text 补
补码除法示例

注意,因为一共左移了4次,所以余数应该是最后得到的余数再乘以242^{-4}


由上述两个除法的例子可见,nn位定点数的除法运算实际上是用2n2n位的数除以一个nn位的数,从而得到nn位的商。
因此需要对被除数进行扩展补0操作。定点正小数在被除数低位补nn个0;nn位无符号数或者定点正整数在被除数高位补nn个0.

C语言类型转换

对于C语言,通常有:

类型16位32 位64位
char111
short int222
int244
unsigned int244
float444
double888
long448
long long888
unsigned long448

有符号和无符号

1
2
3
4
5
6
7
int main(void){
short x = -4321;
unsigned short y = (unsigned short)x;
printf("x = %d, y = %u\n",x,y);
}
// x = -4321, y = 61215
// 1110111100011111
  • 二进制数值相同,只是解释方式发生了变化

字长不同的整数

1
2
3
4
5
6
7
8
9
10
int main(void){
int x = 165537, u = -34991; // int 型占用 4B
short y = (short)x, v = (short)u; // short 型占用 2B
printf("x = %d, y = %d\n",x,y);
printf("u = %d, v = %d\n",u,v);
}
// x = 165537, y = -34991
// u = -34991, v = 30545
// (x) 0x000286a1; (y) 0x86a1
// (u) 0xffff7751; (v) 0x7751
  • 大字长转小字长,高位直接截断
1
2
3
4
5
6
7
8
9
10
11
12
int main(void){
short x = -4321;
int y = x;
unsigned short u = (unsigned short)x;
unsigned int v = u;
printf("x = %d, y = %d\n",x,y);
printf("u = %d, v = %d\n",u,v);
}
// x = -4321, y = -4321
// u = 61215, v = 61215
// (x) 0xef1f; (y) 0xffffef1f
// (u) 0xef1f; (v) 0x0000ef1f
  • 小字长转大字长,高位符号扩展

数据存储与排列

大小端方式

在存储数据时,通常用 LSB 最低有效字节 和 MSB 最高有效字节 来表示数的低位和高位。

现代计算机基本上都采用 字节编址即每个地址编号存放一个字节
而字节的排序方式就各有不同了。通常我们按字节在连续字节序列中的排列顺序进行分类,有:

  1. 大端方式| Big Endian
  2. 小端方式|Little Endian

int 类型的 0x12345678 为例,它占用 4 个字节,假设从地址 0x4000 开始存放,那么:

  • 小端模式(Little-endian)
内存地址0x40000x40010x40020x4003
存放内容0x780x560x340x12
  • 大端方式 (Big-endian)
内存地址0x40000x40010x40020x4003
存放内容0x120x340x560x78

我们的 PC 机上使用的是 X86 结构的 CPU,它是小端模式;
51 单片机是大端模式;
很多 ARM、DSP 也是小端模式(部分 ARM 处理器还可以由硬件来选择是大端模式还是小端模式)。

借助共用体,我们可以检测 CPU 是大端模式还是小端模式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main(void){
// 建立共用体data
union{
int n; // 4B
char ch; // 1B
} data;

data.n = 0x00000001; //也可以直接写作 data.n = 1;

if(data.ch == 1){
printf("Little-endian\n");
}else{
printf("Big-endian\n");
}

return 0;
}

共用体各个成员共用一段内存

0x01 是数据的低位.

  1. 如果 0x01 被存储在 data 的低字节,就是小端模式,即此时 data.ch 的值也是 0x01
  2. 如果 0x01 被存储在 data 的高字节,就是大端模式,此时 data.ch 的值就是 0x00

边界对齐存储

在计算机的机器字长固定之后,最简单的数据存储方式就是按顺序依次存储
而为了节约存储空间,最容易想到的存储方式就是将数据紧密地排列起来,如下图所示:
边界不对齐方式

我们知道,如果像上图一样填充的话,计算机在根据地址访问数据 x 时,需要进行 3 次访存,并且再对高低字节的位置进行调整合并,这极大地影响了指令的执行效率。

因此,计算机中常常使用如下的边界对齐方式对数据进行存储:
边界对齐方式
图中空白的部分是留空的部分,因此边界对齐存储会丢失一部分存储空间。而由于地址都是数据字节的整数倍,所以对于 字节、半字和字 来说,均可以一次访存取出,这提高了运行效率。

我们给出对齐存储的规则如下:

  1. 编译器按成员列表的顺序为每个成员分配内存
  2. 结构的起始存储位置为该结构中边界对齐要求最严格的数据类型所要求的位置
  3. 第一个成员存放在偏移量为0的位置;
    接下来的各成员存放在偏移量为该成员的类型所占字节数的整数倍的位置;
  4. 结构体大小为该结构体中占用空间最大的成员的所占字节数的整数倍

真题考点

此处以 2012年408统考真题 为例进行讲解

某计算机存储器按字节编址,采用小端方式存放数据,假定编译器规定intshort型长度分别为32位和16位,并且数据按边界对齐存储,其C语言程序段如下:

1
2
3
4
5
6
7
struct {
int a;
char b;
short c;
}record;

record.a = 273;

record变量的首地址为0xC008,则地址0xC008中的内容及record.c的地址分别为( )

A . 0x000xC00D

B . 0x00 ,0xC00E

C . 0x11 ,0xC00D

D . 0x11 ,0xC00E

答案

首先,record首地址存放的即是record.a的内容
a=273=0x00000111小端存储,先存放小的那一端,所以存放的是0x11

然后,因为是边界对齐,即对于存放某长度为m字节的数据,存放地址需在m字节的整数倍存放,结构体整体的大小是最大成员长度的整数倍
因此有:

地址0xC0080xC0090xC00A0xC00B
内容record.a(0x11)record.a(0x01)record.a(0x00)record.a(0x00)
地址0xC00C0xC00D0xC00E0xC00F
内容record.b-record.crecord.c

记 首地址0xC008处为偏移量0的单元,则0xC00E处的偏移量6,是sizeof(short)==2整数倍

浮点数的表示与运算

浮点数表示法是指 以适当的形式 将比例因子表示在数据中,让小数点的位置根据需要而浮动。
我们可以回忆小学二年级就学过的 科学记数法 对大数的表示,例如:
19971400000000=1.99714×101319971400000000=1.99714×10^{13}
计算机表达10的幂是一般是用E或e,也就是1.99714E13=19971400000000

那么类似地,对于二进制来说,我们可以将数据表示成:

N=rE×MN=r^E\times M

式中,rr——浮点数的基数,通常取2、4、16等。
EE——阶码,也就是指数,通常用二进制定点整数表示。
MM——尾数,通常用二进制定点小数表示。

可见,尾数的位数决定着浮点数的有效位数,有效位数越多,数据的精度就越高。

规格化

科学记数法中,134×103134\times 10^3是不规范的,需要将其改为1.34×1051.34\times 10^5

类似地,浮点数的规格化就是通过一系列操作使得浮点数的尾数最高位为一个有效值。目的显然是为了尽可能地保留有效数字的位数,从而增加数据的表示精度

上面提到的一系列操作,这里有两种:

  • 左规:当尾数的最高位不是有效位时,需要将尾数左移(就是将小数点右移),直到尾数变成规格化形式为止。该过程同时还伴随着阶码的减小,如果基数是2,则尾数每左移一位,阶码就需要减1。左规可能需要进行多次
  • 右规:对浮点数进行运算时,如果尾数出现有效进位,使得结果不再是小数时,需要将尾数右移(就是将小数点左移),然后阶码加1(基数是2的情况)。对于二进制进位来说,进位结果肯定不会超过1位,因此右规只需进行一次

Tips: 当基数是4时,规格化的尾数最高两位不全为0

溢出判断

当进行浮点数运算时,运算结果大于最大正数时称为 正上溢;结果小于绝对值最大的负数时称为 负上溢。二者统称为 上溢.
数据一旦产生上溢,计算机必须中断运算操作,进行溢出处理。

当进行浮点数运算时,运算结果在0到最小正数之间时 称为 正下溢;结果在0到绝对值最小的负数之间时 称为 负下溢。二者统称为 下溢.
数据下溢时,浮点数值趋于零,计算机将其作为机器数0进行处理。

IEEE 754 标准

根据 IEEE 754 标准,常用浮点数的格式不再是前文介绍的N=rE×MN=r^E\times M,而是更为标准的:

N=(1)S×1.M×rEN=(-1)^S\times 1.M\times r^E

式中,rr——基数隐含为2
EE——阶码,要求用二进制移码表示。
1.M1.M——尾数,通常用二进制 隐藏位策略的原码(定点小数) 表示。
SS——数符,0表示正数,1表示负数。

编码格式

类 型数 符阶 码尾 数 数 值总 位 数偏 置(16进制)偏 置(10进制)
短浮点数1823327FH127
长浮点数11152643FFH1023
临时浮点数11564803FFFH16383

注:上表的 数符、阶码、尾数从左到右的出现顺序,即是计算机中存储浮点数的划分顺序.

  • 短浮点数 即是 单精度、float类型
  • 长浮点数 即是 双精度、double类型

特殊值和偏置值

在 IEEE 754 标准中,除了上述的规格化表示外,还有一些特殊值的表示方法,具体见下表。

阶码尾数描述
0000表示:±0±0(正负取决于符号位)
非规格化0000有效数字的整数部分为固定数值0
规格化[1,2n2][1,2^n−2]任意指数偏置值为2n112^{n-1}−1
无穷2n12^n-100阶码是2n12^n-1(即阶码位全是1),表示:±±\infty(正负取决于符号位)
NaN2n12^n-100表示:不是一个数(NaN
  • 非规格化形式用于表示非常接近0的数,此时的实际尾数区别于规格化的1.M1.M应该是0.M0.M
  • 引入“无穷”的概念是为了使得在计算出现异常时,程序能够继续运行

阶码在IEE754标准中用 移码 表示,其定义是:

  [x]=2n1+xx=[x]2n1\begin{aligned} \;[x]_{\text 移}&=2^{n-1}+x\\ x&=[x]_{\text 移}-2^{n-1} \end{aligned}

因此,想要通过移码计算出实际阶数,我们需要将移码减去偏置值

而通过上面的表格,我们注意到,阶码在IEEE754标准下,全1和全0的情况下都有着特殊的表示含义。
float型数据为例,IEE754标准为其分配了8位作为阶码,因此用移码表示的话,其可选值为:00000000 ~11111111,即 0~ 255,去除表示0和无穷大的两种情况,则为 1~254
如果偏置值取281=1282^{8-1}=128,则阶码的真值为 -127~+126
如果偏置值取127,则阶码的真值为 -126~+127

权衡之下,我们更希望能表示21272^{127}数量级的大数据,因此和真正的移码相比,浮点数的移码的偏置值是不同的。

最终定义:float型的偏置值是127,double型的偏置值是1023

💦结合移码与补码的关系:补码的符号位取反就是移码。
我们可以进一步得出下面的快速解题技巧

  • 当移码符号位是1时,说明阶数为正,根据移码与补码的关系,可将除符号位的移码直接转换为十进制数,之后再将结果+1得到正确的阶数。
  • 当移码符号位是0时,说明阶数为负,根据移码与补码的关系,可将除符号位的移码按位取反后,直接转换为十进制数,之后再带上符号,结果即为正确的阶数。

浮点数的运算

浮点数的运算特点是阶码运算尾数运算分开进行。

  1. 对阶 按照 小阶向大阶看齐原则,将阶码小的尾数右移一位,阶数+1。
    • 其中右移会舍入低位的有效位,影响精度。
  2. 尾数求和 按照定点小数的加减规则直接对尾数进行计算。结果进行规格化
  3. 溢出判断 运算结果是否溢出主要是看结果的指数是否发生上溢。一般地,如果带双符号位进行计算时,阶码的符号位出现 01 则表示发生上溢,10 则表示发生下溢。

舍入

在对阶和右规的过程中,可能会将尾数的低位丢失,从而引起误差,影响精度。

舍入方式的原则

  1. 尽量使误差范围对称,使得平均误差为0.即有舍有入,防止误差积累
  2. 方法要简单,以加快速度

常见的舍入方法

  1. 0舍1入法 类似于十进制的 四舍五入法。如果将被丢弃的值是0就直接舍弃;如果是1则舍弃后在尾数末位+1。这样做可能会使得尾数产生溢出,此时需要继续右规。
  2. 恒置1法 无论将被丢弃的值是1还是0.都将右移后的尾数末位数值置1。
  3. 截断法 直接截取所需位数,丢弃后面的所以位。

实例演示

为了加深的对浮点数的加减运算,此处暂举一例,并用直观算法和机器算法两种方式进行讲解。

C语言的浮点数

C 语言 中的 floatdouble分别对应 IEEE 754 单精度浮点数和双精度浮点数。
long double类型对应与扩展的双精度浮点数,但其长度和格式与编译器和处理器类型有关。

强制转换

  • char -> int -> long -> doublefloat -> double
    以上两种 C 程序中的强制转换,从前到后范围和精度依次增大,转换过程没有损失

  • int -> float
    由于float的尾数包括隐藏位一共只有24位,因此如果int数据超过24位,即其24~31位非0的话,就会在转换过程中舍入低位,影响精度。

  • float/double -> int
    转换时,因为int只表示整数,所以会将小数部分直接截断。另外由于int表示范围更小,所以大数转换时可能发生溢出

  • double -> float
    基本同上。

混合运算时,遵循 “类型提升”原则。

Q: 位数相同的浮点数比定点数可表示的数据个数多吗?

A: nn 位编码只能表示2n2^n 个数。(当然存在有一个值有多个编码对应的情况,所以个数会有少量差异)

参考

  1. 《2021王道计算机组成原理》
  2. 《2023王道计算机组成原理》
  3. 怎么理解Booth算法|知乎
  4. 补码一位乘法的推导
  5. 原码除法运算原理是什么?|电子发烧友网
  6. 原码补码乘除法|PPT
  7. c语言各类型所占字节数|CSDN
  8. 大端方式和小端方式|CSDN
  9. 数据对齐存储|CSDN
  10. 【考研真题】边界对齐存储|CSDN
  11. 啊!啊!啊!IEEE 754移码偏移值的127!|CSDN
  12. IEEE 754标准详解-转载|博客园