1.3 MiB
数据表示与运算习题
数制与编码
进位计数制
十进制转换为R进制
例题 将十进制的$75.3$转换为二进制并保留三位。
首先将$75$拿出来，以基数$2$相除：
$75\div2=37\dots1$，$37\div2=18\dots1$，$18\div2=9\dots0$，$9\div2=4\dots1$，$4\div2=2\dots0$，$2\div2=1\dots0$，$1\div2=0\dots1$，这个顺序是从低位到高位的，所以$75$转换二进制就是$1001011$。
然后是对小数$0.3$的处理：
$0.3\times2=0.6=0+0.6$，$0.6\times2=1.2=1+0.2$，$0.2\times2=0.4=0+0.4$，这个顺序是从高位到低位的，所以$0.3$转换二进制就是$0.010$。
所以转换最后得到$1001011.010B$。
数据校验
例题 设待校验的数据为$D_8\sim D_1=10101011$，若采用海明校验，其海明码为()（设海明码具有一位纠错能力，$P_{13}$采用全校验）。
A.0\,1010\,0\,101\,1\,1\,11
B.0\,1000\,0\,111\,1\,1\,11
解：$A$。题目的重点就是求出校验位。
根据海明不等式，$2^r\geqslant k+r+1$，即$2^r\geqslant 8+r+1$，解得$r=4$，又需要全校验，所以$P_{13}$为全校验位。
所以校验位一共有$P_1$、$P_2$、$P_4$、$P_8$、$P_{13}$（$E_1$、$E_2$、$E_3$、$E_4$、$E_5$）。
因为数据从右到左，所以：
| 数据位 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 编码 | P_{13} |
P_{12} |
P_{11} |
P_{10} |
P_9 |
P_8 |
P_7 |
P_6 |
P_5 |
P_4 |
P_3 |
P_2 |
P_1 |
| 编码 | E_5 |
D_8 |
D_7 |
D_6 |
D_5 |
E_4 |
D_4 |
D_3 |
D_2 |
E_3 |
D_1 |
E_2 |
E_1 |
| 位置二进制 | 1101 | 1100 | 1011 | 1010 | 1001 | 1000 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 |
| 数值 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
接下来就只用求对应的$P$就可以了。
根据$P$位置二进制，$P_1$验证地址第四位为$1$的数据，即$D_1$、$D_2$、$D_4$、$D_5$、$D_7$，$P_1=P_3\oplus P_5\oplus P_7\oplus P_9\oplus P_{11}=D_1\oplus D_2\oplus D_4\oplus D_5\oplus D_7=1$。
$P_2$验证地址第三位为$1$的数据，即$P_2=P_3\oplus P_6\oplus P_7\oplus P_{10}\oplus P_{11}=1=D_1\oplus D_3\oplus D_4\oplus D_6\oplus D_7=1$。
$P_4$验证地址第二位为$1$的数据，即$P_4=P_5\oplus P_6\oplus P_7\oplus P_{12}=D_2\oplus D_3\oplus D_4\oplus D_8=1$。
$P_8$验证地址第一位为$1$的数据，即$P_8=P_9\oplus P_{10}\oplus P_{11}\oplus P_{12}=D_5\oplus D_6\oplus D_7\oplus D_8=0$。
$P_{13}=D_8\oplus D_7\oplus D_6\oplus D_5\oplus E_4\oplus D_4\oplus D_3\oplus D_2\oplus E_3\oplus D_1\oplus E_2\oplus E_1=0$，填入表格：
| 数据位 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 编码 | P_{13} |
P_{12} |
P_{11} |
P_{10} |
P_9 |
P_8 |
P_7 |
P_6 |
P_5 |
P_4 |
P_3 |
P_2 |
P_1 |
| 编码 | E_5 |
D_8 |
D_7 |
D_6 |
D_5 |
E_4 |
D_4 |
D_3 |
D_2 |
E_3 |
D_1 |
E_2 |
E_1 |
| 数值 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
循环冗余校验码
例题 在$CRC$中，接收端检测出某一位数据错误后，纠正的方法是()。
$A.$请求重发
$B.$删除数据
$C.$通过余数值自行纠正
$D.$以上均可
解：$D$。$CRC$可以纠正一位或多位错误（由多项式$G(x)$决定），而实际传输中纠正方法可以按需求进行选择，在计算机网络中，这三种方法都是很常见的。
定点数
定点数表示
无符号数
在计算机中，通常用来表示主存地址的是()。
$A.$移码
$B.$补码
$C.$原码
$D.$无符号数
解：$D$。主存地址都是正数，因此不需要符号位，因此直接采用无符号数表示。
补码
例题 设$[x]_{\text{补}}=1.x_1x_2x_3x_4$，当满足()时，$x<-\dfrac{1}{2}$成立。
$A.x$必须为$1$，$x_2x_3x_4$至少有一个为1
$B.x$必须为$1$，$x_2x_3x_4$任意
$C.x$必须为$0$，$x_2x_3x_4$至少有一个为1
$D.x$必须为$0$，$x_2x_3x_4$任意
解：$D$。$-\dfrac{1}{2}$用补码表示为$1.1000$，使用补码时，符号位相同，数值位越大码值越大，则若$x<-\dfrac{1}{2}$，则$x_1=0$，这样必然小于，其他几位任意。
例题 设$x$为真值，$x^$为其绝对值，满足$[-x^]{\text{补}}=[-x]{\text{补}}$，当且仅当()。
$A.x$任意
$B.x$为正数
$C.x$为负数
$D.$以上说法都不对
解：$D$。当$x=0$或$x$为正数时，$x=x^$，所以$[-x^]{\text{补}}=[-x]{\text{补}}$成立，而当$x$为负数时，$-x^=x$，所以$[-x^]{\text{补}}=[x]{\text{补}}\neq[-x]_{\text{补}}$。所以上面说法都不对。
例题 关于模$4$补码，下列说法正确的是()。
$A.$模$4$补码和模$2$补码不同，它更容易检查乘除运算中的溢出问题
$B.$每个模$4$补码存储时只需一个符号位
$C.$存储每个模$4$补码需要两个符号位
$D.$模$4$补码，在算术与逻辑部件中为一个符号位
解：$B$。模$4$补码即用两位符号位来代替一位符号位，常用于补码的运算。模$4$补码具有模$2$补码的全部优点且更易检查加减运算中的溢出问题，$A$错误。需要注意的是，存储模$4$补码仅需一个符号位，因为任何一个正确的数值，模$4$补码的两个符号位总是相同的，$B$正确。只在把两个模$4$补码的数送往$ALU$完成加减运算时，才把每个数的符号位的值同时送到$ALU$的双符号位中，即只在$ALU$中采用双符号位，$C$、$D$错误。
定点数运算
定点数移位运算
例题 若$[X]_{\text{补}}=X_0X_1\cdots X_n$，其中$X_0$为符号位，$X_1$为最高数位。若()，则当补码左移时，将会发生溢出。
A.X_0=X_1
B.X_0\neq X_1
C.X_1=0
D.X_1=1
解：$B$。其实就是溢出如何判断。溢出判别法有两种适用于此种情况:一是加一个符号位变为双符号位，然后左移，若两符号位不同则溢出，因此$X_0\neq X_1$时溢出；二是数值位最高位进位和符号位进位不同则溢出，同样可知$X_0\neq X_1$时溢出。
例题 一个$8$位寄存器内的数值为$11001010$，进位标志寄存器$C$为$0$，若将此8位寄存器循环左移（不带进位位）$1$位，则该$8$位寄存器和标志寄存器内的数值分别为()。
A.10010100\,1
B.10010101\,0
C.10010101\,1
D.10010100\,0
解：$C$。不带进位位的循环左移将最高位进入最低位和标志寄存器$C$位，所以高位$1$进入了进位位，也变为了数值的末尾。如果带则进位位的数据一同进行循环左移。
定点数加减运算
例题 有符号整数加减、无符号整数加减运算，这四种运算能否利用同一个加法器辅助电路实现？简述理由。
解：能。$n$位加法器实现的是模$2^n$无符号整数加法运算。（即二进制加减时需要考虑$n$位之间的借位和进位，这是一般的二进制加减法，如果是模二运算则相当于对每位进行异或运算，不需要考虑各位之间的借位和进位，如之前的$CRC$校验码运算）
对于无符号整数$a$和$b$，对$a+b$可以直接用加法器实现，而$a-b$可用$a$加$-b$的补码实现，即$a-b=a+[-b]_{\text{补}}$（$\mod 2^n$），这是因为$a-b$如果不发生溢出则$a-b>0$，$a-b$的原码也是补码，所以原码计算可以使用补码计算来达成，所以$n$位无符号整数加减运算都可在$n$位加法器中实现，辅助电路逻辑用于计算减数$b$的相反数的补码。
由于有符号整数用补码表示，补码加减运算公式为$[a+b]{\text{补}}=[a]{\text{补}}+[b]{\text{补}}$（$\mod 2^n$），$[a-b]{\text{补}}=[a]{\text{补}}+[-b]{\text{补}}$（$\mod 2^n$），所以$n$位有符号整数加减运算都可在$n$位加法器中实现，辅助电路逻辑用于计算减数$b$的相反数的补码。
所以辅助电路在原码补码减肥中都起到同样的效果。
例题 设机器字长为$8$位含一位符号位，$A=15$，$B=-24$，求$A+B$和$A-B$的补码。
解：$A=+1111$，从而原码补码为$0000,1111$，$B=-11000$，所以原码为$1001,1000$，反码为$1110,0111$，补码为$1110,1000$。
所以$A+B$的补码等于$A$的补码加$B$的补码，$=0000,1111+1110,1000=1111,0111$，原码就是$1000,1001$，即$-9$，这与预期的一样。
同理负数值的补码就是补码全部取反加$1$，所以$A-B=0000,1111+0001,1000=0010,0111$，即$+39$。
定点数乘法运算
原码一位乘法：符号位异或，取绝对值相乘。
例题 设机器字长为$n+1=5$位（含$1$位符号位），其中$x$的原码为$1.1101$，$y$的原码为$0.1011$，采用原码一位乘法求$x\cdot y$。
解：其中$x$就是$-0.1101$，而$y$就是$+0.1011$。先抛去符号位的正负全部为正，就得到$01101$和$01011$两个数据。
将$MQ$、$ACC$、$X$都初始化为五位存储单元。$X$放入被乘数$01101$，$MQ$放入乘数$01011$，$ACC$为$00000$。
ACC MQ 丢失位
0 0 0 0 0 <--> ^ 0 1 0 1 1 |
|
ALU
|
0 1 1 0 1
X
运算器结构：$ACC$与$MQ$相连，数据流是双向的，$ACC$与$ALU$相连，数据流是双向的，$X$的数据流向$ALU$。
此时$MQ=01011$，作为乘法单位的最后位为$1$，所以$ACC+=X$，从而$ACC=00000+01101=01101$，这就是第一个的位积。（其中^左边的即计算的结果，即部分积）
ACC MQ 丢失位
0 1 1 0 1 <--> ^ 0 1 0 1 1 |
|
ALU
|
0 1 1 0 1
X
由于按照乘法规则，第二个位积计算时需要错位相加，计算机的处理方式是$ACC$和$MQ$的数据连在一起，全部逻辑右移一位（左边补$0$）。
ACC MQ 丢失位
0 0 1 1 0 <--> 1 ^ 0 1 0 1 | 1
|
ALU
|
0 1 1 0 1
X
所以$ACC$的数据由$01101$变为$00110$，最后的$1$移到$MQ$最高位，$MQ$由$01011$变为$10101$，最后的一位$1$溢出被抛弃，代表这一位的位积已经计算并相加完成，所以不用管了。此时结果的高位还在$ACC$中，而结果的低位从$ACC$移到了$MQ$中，在$MQ$的低位也不参与后面的运算，所以也不用管了。
然后计算下一个最低位的位积，此时$MQ$的最低位还是$1$，所以$ACC+=X=00110+01101=10011$。
ACC MQ 丢失位
1 0 0 1 1 <--> 1 ^ 0 1 0 1 | 1
|
ALU
|
0 1 1 0 1
X
同样计算完后再错位，进行逻辑右移，$ACC$由$10011$变成了$01001$，$MQ$由$10101$变成了$11010$，最低位的$1$被抛弃，此时$MQ$中已经有两个结果最低位。
ACC MQ 丢失位
0 1 0 0 1 <--> 1 1 ^ 0 1 0 | 1 1
|
ALU
|
0 1 1 0 1
X
此时$MQ$最低位为$0$，所以$ACC$保持不变，再逻辑右移一位，$ACC$由$01001$变为$00100$，$MQ$由$11010$变为$11101$，抛弃一位$0$，$MQ$有三个结果最低位。
ACC MQ 丢失位
0 0 1 0 0 <--> 1 1 1 ^ 0 1 | 0 1 1
|
ALU
|
0 1 1 0 1
X
此时$MQ$最低位为$1$，则$ACC+=X=00100+01101=10001$。
ACC MQ 丢失位
1 0 0 0 1 <--> 1 1 1 ^ 0 1 | 0 1 1
|
ALU
|
0 1 1 0 1
X
同样计算完后再错位，进行逻辑右移，$ACC$由$10001$变成了$01000$，$MQ$由$11101$变成了$11110$，最低位的$1$被抛弃，此时$MQ$中已经有四个结果最低位，此时$MQ$最低位是代表符号的$0$不参与运算。此时计算已经结束。
ACC MQ 丢失位
0 1 0 0 0 <--> 1 1 1 1 ^ 0 | 1 0 1 1
|
ALU
|
0 1 1 0 1
X
小数的小数点隐藏在第一位的后面，所以此时结果在$ACC$和$MQ$的前四位中，即$0.10001111$。最后加上符号异或结果$x\oplus y=0\oplus1=1$，得到$1.10001111$。
上面是计算具体的物理逻辑过程，逻辑的求解过程如下：
被乘数在$X$中，其结果在每次的第三行，左边的第一行为$ACC$没有右移的结果，第二行为右移的结果，右边的为$MQ$的内容。原码一位乘法可以使用单符号位也可以使用双符号位。
补码一位乘法
例题 设机器字长为$n+1=5$位（含$1$位符号位），其中$x$的原码为$-0.1101$，$y$的原码为$+0.1011$，采用补码一位乘法求$x\cdot y$。
解：
由于需要使用补码，且需要$-x$的补码，所以$[x]{\text{补}}=1.0011$，$[-x]{\text{补}}=0.1101$，$[y]_{\text{补}}=0.1011$。
将$MQ$、$ACC$、$X$都初始化为六位存储单元。$ACC$和$X$都使用双符号位补码，$MQ$使用单符号位补码，$X$放入被乘数补码$11.0011$，$MQ$放入乘数补码$00.1011$，$ACC$为$000000$。辅助位初始化为$0$。
ACC MQ 辅助位 丢失位
0 0 0 0 0 0 <--> 0 1 0 1 1 | 0 |
|
ALU
|
1 1 0 0 1 1
X
其中下划线的左边一个为$MQ$最低位，右边一个为辅助位，根据辅助位-$MQ$最低位判断加的是$x$补码的哪个值。
是双符号位，但是右移时将两个符号位视为一个一起移动。
最后一次再根据条件判断加什么，加后不需要右移即是结果（这里让符号位参与运算）。当被乘数全部移出部分积计算结束。（$n$轮，$n$为数值位）
所以$x\cdot y=-0.10001111$。
例题 有实现$x\times y$的两个$C$语言函数如下：
unsigned umul(unsigned x, unsigned y){
return x*y;
}
int imul(int x, int y){
return x*y;
}
假定某计算机$M$中的$ALU$只能进行加减运算和逻辑运算。请回答下列问题。
1）若$M$的指令系统中没有乘法指令，但有加法、减法和位移等指令，则在$M$上也能实现上述两个函数中的乘法运算，为什么？
2）若$M$的指令系统中有乘法指令，则基于$ALU$、位移器、寄存器及相应控制逻辑实现乘法指令时，控制逻辑的作用是什么？
3）针对以下三种情况: 1）没有乘法指令；2）有使用$ALU$和位移器实现的乘法指令；3）有使用阵列乘法器实现的乘法指令，函数umul()在哪种情况下执行的时间最长？在哪种情况下执行的时间最短？说明理由。
4）$n$位整数乘法指令可保存$2n$位乘积，当仅取低$n$位作为乘积时，其结果可能会发生溢出。当$n=32$、$x=2^{31}-1$、$y=2$时，带符号整数乘法指令和无符号整数乘法指令得到的$x\times y$的$2n$位乘积分别是什么（用十六进制表示）？此时函数umul()和imul()的返回结果是否溢出？对于无符号整数乘法运算，当仅取乘积的低$n$位作为乘法结果时，如何用$2n$位乘积进行溢出判断？
解：这是一个关于乘法实现的概念题目。
1）乘法运算可以通过加法和移位来实现。编译器可以将乘法运算转换为一个循环代码段， 在循环代码段中通过比较、加法和移位等指令实现乘法运算。
2）控制逻辑的作用是控制循环次数，控制加法和移位操作。
3）1）最长，3）最短。对于1），需要用循环代码段（即软件）实现乘法操作，因而需要反复执行很多条指令，而每条指令都需要取指令、译码、取数、执行并保存结果，所以执行时间很长；对于2）和3），都只需用一条乘法指令实现乘法操作，不过2）中的乘法指令需要多个时钟周期才能完成，而3）中的乘法指令可在一个时钟周期内完成，所以3）的执行时间最短。
4）这个题目讨论溢出的问题。当$n=32$、$x=2^{31}-1$、$y=2$时，可以保存$2n=64$位乘积，结果为$2^{32}-2$，因为为正数，所以带符号整数和无符号整数乘法指令得到的$64$位乘积都是$0000,0000,FFFF,FFFEH$。$int$型的表示范围为$[-2^{31},2^{31}-1]$，故函数imul()的结果溢出；$unsigned,int$型的表示范围为$[0,2^{32}-1]$，故函数umul()的结果不溢出。对于无符号整数乘法，若乘积高$n$位全为$0$，即使低$n$位全为$1$也正好是$2^{32}-1$，不溢出，否则溢出。
定点数除法运算
原码恢复余数法
例题 设机器字长为$5$位（含一位符号位），$x=0.1011$，$y=0.1101$，采用原码恢复余数法求$x\div y$。
其中$x$就是$+0.1011$，而$y$就是$+0.1101$。先抛去符号位，就得到$01011$和$01101$两个数据。然后求出$\vert y\vert$的补码：$01101$和$-\vert y\vert$的补码：$10011$。
为什么是原码却要求补码？因为在除法中，每一步都要将当前部分被除数$x_i$与这个位的部分商$q_i=[0|1]$与除数$y$相乘得到的乘积$p=q_i\times y$相减得到余数即下一个被除数$x_{i+1}$。
所以需要用到原码的减操作，但是原码不好进行减操作运算，补码更容易进行减操作运算。
而对于补码的减操作$[x_i-p]{\text{补}}=[x_i+(-p)]{\text{补}}=[x_i]{\text{补}}+[-p]{\text{补}}$，又在除法中是要找让与除数的乘积最大且不超过被除数的余数，所以$x_i>p$必然成立，所以$x_i-p>0$必然成立，而正数的补码和原码相等，所以$[x_i-p]{\text{原}}=[x_i-p]{\text{补}}=[x_i]{\text{补}}+[-p]{\text{补}}$。
将$MQ$、$ACC$、$X$都初始化为五位存储单元。将被除数$01011$放入$ACC$中，将除数$01101$放入$X$中，商在$MQ$初始化为$00000$。当前要确定的商的位数是$MQ$中最低一位。
ACC MQ
0 1 0 1 1 <--> 0 0 0 0 0 ^
|
ALU
|
0 1 1 0 1
X
手算时每位商取$0/1$是通过心算判断当前余数和除数的大小确定的。而机器实现时就要通过$ALU$判断是$ACC$中的数更大还是$X$中的数更大，如果$ACC$的更大就商$1$，若$X$的更大就商$0$。（商应该让乘积小于当前$ACC$中的被除数$x_i$）
但是实际上恢复余数法中计算机每次会默认商$1$，如果错误（$ACC$得到的结果为负数）再修改为商$0$，并且恢复余数。
第一位默认商$1$，$ACC-=X$，$ACC$的$01011$和$X$的$10011$（$x$实际值的负值的补码）输入$ALU$进行加操作$01011+10011=11110$，返回给$ACC$，此时发现代表符号的最高位为$1$，代表出现了负数，就表明之前的商出错了（因为我们去掉了符号，所以除数与被除数都是正数不可能是负数）。
ACC MQ
1 1 1 1 0 <--> 0 0 0 0 ^ 1
|
ALU
|
0 1 1 0 1
X
所以重新确定商为$0$，$ACC$要恢复余数，从而再加上$y$的补码：$11110+01101=01011$。（因为原来加上了$-y$的补码，相当于减去了$y$，此时加上$y$结果重新变成了正数，正数的补码等于正数的原码）
ACC MQ
0 1 0 1 1 <--> 0 0 0 0 ^ 0
|
ALU
|
0 1 1 0 1
X
第一位的商计算完后需要进行计算，错位相除，所以同乘法一样，$ACC$和$MQ$的值都要逻辑左移一位，低位补$0$，所以$MQ$由$00000$还是变为$00000$，$MQ$的最高位的$0$移到$ACC$最低位，$ACC$最高位丢弃，由$01011$变成$10110$。
ACC MQ
1 0 1 1 0 <--> 0 0 0 ^ 0 0
|
ALU
|
0 1 1 0 1
X
然后第二位默认商$1$，同样$ACC-=X$，$10110+10011=01001$（高位溢出直接丢弃），将这个值赋给$ACC$，发现符号位为$0$，代表正，商就没有问题，$MQ$为$00001$。
ACC MQ
0 1 0 0 1 <--> 0 0 0 ^ 0 1
|
ALU
|
0 1 1 0 1
X
再次逻辑左移一位，$MQ$由$00001$变为$00010$，$ACC$由$01001$变为$10010$。
ACC MQ
1 0 0 1 0 <--> 0 0 ^ 0 1 0
|
ALU
|
0 1 1 0 1
X
第三位默认商$1$，同样$ACC-=X$，$10010+10011=00101$，商没有问题，$MQ$为$00011$。
ACC MQ
0 0 1 0 1 <--> 0 0 ^ 0 1 1
|
ALU
|
0 1 1 0 1
X
再次逻辑左移一位，$MQ$由00011$变为$00110$，$ACC$由$00101$变为$01010$。
ACC MQ
0 1 0 1 0 <--> 0 ^ 0 1 1 0
|
ALU
|
0 1 1 0 1
X
第四位默认商$1$，同样$ACC-=X$，$01010+10011=11101$，高位为$1$。
ACC MQ
1 1 1 0 1 <--> 0 ^ 0 1 1 1
|
ALU
|
0 1 1 0 1
X
商应该为$0$，$MQ$变为$00110$，$ACC$恢复余数：$11101+01101=01010$。
ACC MQ
0 1 0 1 0 <--> 0 ^ 0 1 1 0
|
ALU
|
0 1 1 0 1
X
再次逻辑左移一位，$MQ$由$00110$变为$01100$，$ACC$由$01010$变为$10100$。
ACC MQ
1 0 1 0 0 <--> ^ 0 1 1 0 0
|
ALU
|
0 1 1 0 1
X
第五位默认商$1$，同样$ACC-=X$，$10100+10011=00111$，高位为$0$，商没有问题，$MQ$为$01101$。
ACC MQ
0 0 1 1 1 <--> ^ 0 1 1 0 1
|
ALU
|
0 1 1 0 1
X
此时计算结束，商为$01101$，并乘上$x\oplus y=0\oplus0=0$为正数，所以商还是$01101$。余数为$00111$，余数还要乘上$2^{-n}=2^{-4}$才为真值（$n$为除法步骤轮次或数值位）。
原码的加减交替法：
不恢复余数法本质只是将恢复余数法的流程进行压缩整合，原理是一样的，因为减去加上同一个值很浪费时间所以对其进行优化。如上面的计算例子，定义$+[-\vert y\vert]{\text{补}}=-$，$+[\vert y\vert]{\text{补}}=+$，左移为$<$，设$y$绝对值补码为$b$：
| 序号 | 操作 | 被除数/余数 | 商 | 说明 |
|---|---|---|---|---|
| 1 | 0.1011 | |||
| 2 | - | 1.1110 | 0 | 结果为负，设余数为a，商0 |
| 3 | + | 0.1011 | 0 | a+b，恢复余数 |
| 4 | < | 1.0110 | 0 | (a+b)×2=2a+2b |
| 5 | - | 0.1001 | 0 | 2a+2b-b=2a+b |
从第二步减去除数绝对值$b$后就能根据结果判断当前位商$0$，然后$3$步加上绝对值恢复余数，一加一减浪费时间，可以直接从第二步跳到第五步。即如果出现负数余数不用恢复余数，将余数$a$左移一位加上$y$绝对值补码（原码）为$b$就得到下一轮的结果，然后直接对结果判断商。
余数为负，则商$0$，左移，加上除数绝对值；余数为正，则商$1$，左移，减去除数绝对值。
如上个例题使用原码加减交替法：
如果最后一步余数位负，则需要商$0$，并加上$y$绝对值进行恢复余数。
补码除法（不恢复余数法/加减交替法），异号相除是看够不够减，然后上商$1$，够减商$0$，不够减商1。
补码的加减交替法：
与原码加减交替法类似，被除数、除数、余数要使用双符号位，符号位也参与运算。
例题 设机器字长为$5$位（含一位符号位），$x=+0.1000$，$y=-0.1011$，采用补码加减交替法求$x\div y$。
解：首先计算对应的补码，$[x]{\text{补}}=00.1000$，$[y]{\text{补}}=11.0101$，$[-y]_{\text{补}}=00.1011$。
原码的加减交替法第一步就是减去$y$绝对值的补码然后根据商进行判断，而补码的加减交替法首先就要判断，如果被除数除数同号，则被除数减去除数；异号则被除数加上除数。
得到余数后与除数符号进行判断，余数和除数同号，则商$1$，余数左移一位减去除数，余数和除数异号，商$0$，余数左移一位加上除数。重复$n$次。
除了第一步原码加减交替法是固定减法，其他的基本上两个方法是一样的。
所以第一步，由于$xy$是异号的，所以第一步是$x+y=00.1000+11.0101=11.1101$。由于除数符号也是$11$，所以同号商$1$，左移并减去除数，$11.1010+00.1011=00.0101$。
第二步，由于余数符号为$00$，而除数符号为$11$，所以异号，从而商$0$，左移并加上除数，$00.1010+11.0101=11.1111$。
第三步，由于余数符号为$11$，而除数符号为$11$，所以同号，从而商$1$，左移并减去除数，$11.1110+00.1011=00.1001$。
第四步，由于余数符号为$00$，而除数符号为$11$，所以异号，从而商$0$，左移并加上除数（注意这里双符号位就发生了异号，但是不影响），$01.0010+11.0101=00.0111$。
第五步，由于余数符号为$00$，而除数符号为$11$，所以异号，从而商$0$，但是这是最后这一位默认商$1$，所以不商$0$而是$1$。
所以商为$1.0101$，余数为$0.0111\times2^{-4}$（注意这里还是要乘一个$2^{-n}$）。
定点数强制类型转换
例题 一个$C$语言程序在一台$32$位机器上运行。程序中定义了三个变量$x$、$y$、$z$，其中$x$和$z$为$int$型，$y$为$short$型。当$x=127$、$y=-9$时，执行赋值语句$z=x+y$后，$x$、$y$、$z$的值分别是()。
A.x=0000007FH,y=FFF9H,z=00000076H
B.x=0000007FH,y=FFF9H,z=FFFF0076H
C.x=0000007FH,y=FFF7H,z=FFFF0076H
D.x=0000007FH,y=FFF7H,z=00000076H
解：$D$。首先由$x$和$z$为$int$型，$y$为$short$型，知道经过这个运算，要把$short$型变为$int$型再运算。且记住$C$语言的数据在内存中是补码形式。$x$为$32$位，所以为$0000,0007FH$，而$y$为$short$就是$16$位，所以按四位的话，原码为$1101$，补码为$1011$，即$7$，所以$16$位前面全部是$1$，为$FFF7H$。当计算$z=x+y$时，将$y=007FH$转为$32$位，就是前面加$16$位的$1$：$y=FFFF,FFF7H$，执行加法：$0000,007FH+FFFF,FFF7H=0000,0076H$。（其中$F+7=16H$，不断向前进$1$，最高位$1$自然丢弃）
定点数数据存储与排列
例题 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定$int$和$short$型长度分别为$32$位和$16$位，并且数据按边界对齐存储。某$C$语言程序段如下：
struct {
int a;
char b;
short c;
} record;
record.a=273;
若$record$变量的首地址为$0xC008$，则地址$0xC008$中的内容及$record.c$的地址分别为()。
$A.0x00$、0xC00D
$B.0x00$、0xC00E
$C.0x11$、0xC00D
$D.0x11$、0xC00E
解：$D$。记住这里使用了边界对齐，即数据长度必然是$4B$的整数倍。而这里$record$长度为$32(a)+8(b)+16(c)=7B$，所以边界对齐后就有$8B$，有$1B$是填充的。又$record.a=273=256+16+1=0001,0001,0001=0x0000,0111$，采用小端模式，即$0xC008$作为首地址应该存放低地址的内容，即$0x11$。由于字节填充，所以$b$后面有$1B$的填充，所以$record.c$在$14$这个地方，即$0xC00E$。
| 地址 | 0xC008 | 0xC009 | 0xC00A | 0xC00B | 0xC00C | 0xC00D | 0xC00E | 0xC00F |
|---|---|---|---|---|---|---|---|---|
| record.a(0x11) | record.a(0x01) | record.a(0x00) | record.a(0x00) | record.b | 填充 | record.c | record.c |
浮点数
浮点数表示
阶码与尾数
例题 若阶码和尾数都使用补码表示，求对应真值：$a=0,01;1.1001$。
解：$a$的阶码为$0,01$，是正数，所以补码与原码一样，从数值来看就是$+1$。而尾数$1.1001$代表负数，补码为反码加$1$，所以原码为$1,0110+1=1,0111$，即真值$=-(0.25+0.125+0.0625)$。所以$a$的真值就是$2\times(-0.0111)=-0.111=-0.875$（相当于乘$2$左移一位）。
尾数规格化
例题 $a=010;00.1100$，$b=010;00.1000$，求$a+b$的值。
解：已知分号前面的是阶码，后面是尾数，所以$a$和$b$都是$2$的$010=2$次幂。
由尾数的$00$代表$a$和$b$都是双符号位表示且都是正数。
所以$a=2\times2\times00.1100$，$b=2\times2\times00.1000$，则$a+b=2\times2\times00.1100+2\times2\times00.1000=2\times2\times(00.1100+00.1000)=2\times2\times01.0100$。
因为使用双符号位表示时，$00$代表正号，$11$表示负号，$01$时，称为上溢，为$10$时，称为下溢，此时结果为$01$，表示出现了上溢，这时候就需要右规。
阶码加一，变成$2$的三次方，尾数右移一位$=2\times2\times2\times00.1010$。最后结果就是$011;01010$。
例题 若某浮点数的阶码、尾数用补码表示，共$4+8$位：$0,110;1.1110100$，如何规格化？
解：只需要对尾数部分处理，由于负数的补码是$1.0$开头，而这时是$1.1$开头，所以必须变成$1.0$。
补码算术左移低位补$0$，补码算术右移，高位补$1$。如果是算术右移，则会一直补$1$，而无法变成$1.0$开头，所以要使用算术左移，移动三位得到$1.0100000$，同时阶码减$3$变为$3$，最后规格化结果为$0,011;1.0100000$。
IEEE 754标准
格式表示
例题 将十进制数$-0.75$转换为$IEEE,754$的单精度浮点数格式表示。
解：将$-0.75D$首先转换为二进制为$-0.11B$，然后规格化变为$-1.1B\times0.1B$。其中阶码为$-1$（$0.1B$就是代表$2$的负一次方）。
因为是负数，所以数符为$1$，尾数部分应该是将$1.1B$截断隐含的最高位$1$，所以应该用$0.1B$表示，即$.100\cdots$。
由于阶码为$-1$，所以移码=阶码真值+偏置量$=-1+111,1111=0111,1110$。
所以最后就是$1,0111,1110,1000,0000,0000,0000,0000,000$。
例题 $float$型数据通常用$IEEE,754$单精度浮点数格式表示。若编译器将$float$型变量$x$分配在一个$32$位浮点寄存器$FR1$中，且$x=—8.25$，则$FR1$的内容是()。
A.C104\,0000H
B.C242\,0000H
C.C184\,0000H
D.C1C2\,0000H
解：$A$。首先将$x$变为原码，$-8.25=-(8+0.25)=-1000.01=-2^3\times1.00001$。尾数最高位隐藏$1$，所以尾数为$0.00001$，然后计算阶码，$3=0000,0011+0111,1111=1000,0010$。所以$IEEE,754$表示为$1;1000,0010;0000,1000,\cdots=1100,0001,0000,0100,\cdots=C104,0000H$。注意最高位要隐含一个$1$。
转换真值
例题 $IEEE,754$的单精度浮点数$C0,A0,00,00H$的值是多少。
解：首先是$16$进制转二进制，每一个十六进制位转换为四个二进制位。所以得到$1100,0000,1010,0000,0000,0000,0000,0000$。
根据$IEEE,754$标准，将$32$位分割为数符、阶码、尾数三个部分：数符为$1$，阶码为$100,0000,1$，尾数为$010,0000,0000,0000,0000,0000$。
由于尾数最高位隐含为$1$，所以尾数的真值为$1.010,0000,0000,0000,0000,0000$。
由于数符为$1$，则这个数表示的是一个负数。
由于阶码由移码表示，所以看作无符号数就是$129D$，而单精度浮点数的偏移量为$127D$，所以移码真值=移码-偏置量$=1000,0001-0111,1111=0000,0010=2$。
所以浮点数的真值为$-1.01B\times2\times2=-1.25\times4=-5$。
标准表示范围
例题 $float$类型（即$IEEE,754$单精度浮点数格式）能表示的最大正整数是()。
A.2^{126}-2^{103}
B.2^{127}-2^{104}
C.2^{127}-2^{103}
D.2^{128}-2^{104}
解：$D$。表示是正数最大值，所以$S$为符号位可以不用考虑。阶码$E$是八位，所以表达的值是$1\sim254$（规定$255$和$0$都不可以使用），又使用移码加$127$，所以实际上表达的值是比原码小的，即表达最大值为$254-127=127$。尾数为$23$位，又隐藏最高位$1$，所以一共$24$位，正数的最大值为$1.11\cdots1$，所以能表达的最大正整数值为$1.11\cdots\times2^{127}=(2-2^{23})\times2^{127}=2^{128}-2^{104}$。
浮点数运算
浮点数运算过程
例题 下列关于对阶操作说法正确的是()。
$A.$在浮点加减运算的对阶操作中，若阶码减小，则尾数左移
$B.$在浮点加减运算的对阶操作中，若阶码增大，则尾数右移;若阶码减小，则尾数左移
$C.$在浮点加减运算的对阶操作中，若阶码增大，则尾数右移
$D.$以上都不对
解：$C$。从计算规律来看，$ABC$说法都正确，应该选最全面的$B$。但是实际上对阶应该小阶向大阶对齐，所以只能阶码增大，而不能阶码减小。
例题 下列关于各种移位的说法正确的是()。
Ⅰ.假设机器数采用反码表示，当机器数为负时，左移时最高数位丢$0$，结果出错；右移时最低数位丢$0$，影响精度
Ⅱ.在算术移位的情况下，补码左移的前提条件是其原最高有效位与原符号位要相同
Ⅲ.在算术移位的情况下，双符号位的移位操作只有低符号位需要参加移位操作
$A.$Ⅰ、Ⅲ
$B.$仅Ⅱ
$C.$只有Ⅲ
$D.$Ⅰ、Ⅱ、Ⅲ
解：$D$。对于Ⅰ负数的反码除符号位外其他位与负数的原码相反，所以丢$0$就是丢原码的$1$，不难推出Ⅰ正确。如$5$位反码$10010$表示$-13$，右移$1$位变成$11001$为$-6$，影响精度，左移$1$位变成$10101$为$-10$，数据丢失。对于Ⅱ补码表示时，正数的符号位为$0$，左移最高位为$0$时，数据不会丢失；负数的符号位为$1$，左移最高位为$1$时，数据不会丢失。因此左移移走的最高位要与符号位相同。对于Ⅲ，双符号位的最高符号位代表真正的符号，而低位符号位用于参与移位操作以判断是否发生溢出，不用参与运算。
例题 下列关于舍入的说法，正确的是()。
Ⅰ不仅仅只有浮点数需要舍入，定点数在运算时也可能要舍入
Ⅱ.在浮点数舍入中，只有左规格化时可能要舍入
Ⅲ.在浮点数舍入中，只有右规格化时可能要舍入
Ⅳ．在浮点数舍入中，左、右规格化均可能要舍入
Ⅴ．舍入不一定产生误差
$A.$Ⅰ、Ⅲ、Ⅴ
$B.$Ⅰ、Ⅱ、Ⅴ
$C.$Ⅴ
$D.$Ⅰ、Ⅳ
解：$C$。舍入是浮点数的概念，定点数没有舍入的概念，因此Ⅰ错误。浮点数舍入的情况有两种：对阶、右规格化（不可能左规格化，不然可能溢出），因此Ⅱ、Ⅲ、Ⅳ错误。舍入不一定产生误差，如向下舍入$11.00$到$11.0$时是没有误差的，因此Ⅴ正确。
浮点数加减
例题 已知十进制数$X=-\dfrac{5}{256}$，$Y=+\dfrac{59}{1024}$，按机器补码浮点运算规则计算$X-Y$，结果用二进制表示，浮点数格式如下︰阶符取$2$位，阶码取$3$位，数符取$2$位，尾数取$9$位。
解：首先要将十进制的真值转换为二进制原码。因为不是$IEEE,754$标准，所以小数不用转换为$1.xxx$的格式，转成$0.xxx$的格式就可以了：$5D=101B$，$\dfrac{1}{256}=2^{-8}$，所以$X=-101\times2^{-8}=-0.101\times2^{-5}=-0.101\times2^{-101B}$。然后$59D=11 1011B$，$\dfrac{1}{1024}=2^{-10}$，从而$Y=+11 1011\times2^{-10}=0.111011\times2^{-4}=0.111011\times2^{-100B}$。
$X$的阶码为$-101$，转换为补码表示为$1011$，由于使用双符号位，所以变成$11011$；$X$的尾数为$-0.101$，补码表示为$1.011$，由于双符号位，所以为$11.011$，尾数取$9$位，所以拓展为$11.0110,0000,0$。所以$X$就是$11011,11.011000000$。
同理$Y$的阶码为$-100$，转换为补码表示为$1100$，双符号位所以变为$11100$；$Y$的尾数为$0.111011$，补码表示为$0.111011$，使用使用双符号位为$00.111011$，拓展为$9$位得到$00.111011000$。所以$Y$就是$11100,00.111011000$。
然后是阶数对齐，小阶向大阶靠拢。首先求阶差：$11011-11100=11011+00100=11111=11,001=-1D$。所以$X$的阶数比$Y$的阶数小一。所以对$X$尾数算术右移一位，负数高位补$1$，阶码加一，从而由$11011,11.011000000$变为了$11100,11.101100000$。即变为了$-0.0101×2^{-100B}$。
然后是尾数加减，$Y$的尾数需要变成其负值的补码，方法是对尾数包括符号位全部取反，然后末尾加$1$，所以$-Y=11100,11.000101000$。进行相加得到$10.110001000$。这时候代表出现上溢出（用二进制计算尾数变成$-1.001111$，由于定点小数无法表示绝对值大于等于$1$的数，所以上溢）。
第三步规格化，因为使用双符号位，所以正好能补救计算结果的上溢，可以通过右规的方式规格化。所以将$10.110001000$算术右移，将符号位的0以及后面的数据全部右移一位，符号位补成$11$，得到$11.011000100$。然后阶码由于右移而加一，最后为$11101,11.011000100$。
第四步舍入，由于第三步右移抛弃的是$0$，所以没有丧失精度，就不需要舍入。
第五步判溢出，$11101$加$1$后等于$11110$，符号位都是$11$，所以没有溢出。
最后真值为$11101,11.011000100$。即$2^{-3}\times(-0.1001111)_2$。
浮点数强制类型转换
例题 假定变量$i$、$f$和$d$的数据类型分别为$int$、$float$和$double$（$int$用补码表示，$float$和$double$分别用$IEEE,754$单精度和双精度浮点数格式表示），已知$i=785$、$f=1.5678E3$、$d=1.5E100$，若在$32$位机器中执行下列关系表达式，则结果为真的是()。
Ⅰ.$i=(int)(float)i$
Ⅱ.$f=(float)(int)f$
Ⅲ.$f=(float)(double)f$
Ⅳ.$(d+f)-d=f$
$A.$仅Ⅰ和Ⅱ
$B.$仅Ⅰ和Ⅲ
$C.$仅Ⅱ和Ⅲ
$D.$仅Ⅲ和Ⅳ
解：$B$。已知$32$位机器，所以$int$为$32$位，$float$为$32$位，$double$为$64$位。对于$IEEE,754$标准，$float$类型的尾数为$23$位，$double$类型的尾数为$52$位。对于Ⅰ，虽然$float$类型尾数只有$23$位小于$int$类型的$32$位，但是$i=785<2^{10}=1024$，所以$i$只需要$10$位就可以表示，$23>10$，所以这题的$i$转为$f$是无损转换。Ⅱ，计算$f$的真值，$f=1.5678\times10^3=1567.8$不为整数，所以$f$转为$int$类型必然丢失小数点后一位造成不相等，所以Ⅱ错误。$int$和$float$转为$double$都是无损转换，所以Ⅲ正确。对于Ⅳ，左边经过运算后长度短的向长度高的对齐，左边计算后变成了$double$类型，浮点数计算首先要对阶，$f$的阶为$3$，而$d$的阶为$100$，所以$f$的尾数需要右移$100-3=97$位，这就远远超过了$d$所能表示的最大精度$53$，造成$f$后面的小数尾数$.5678$全部丢失，最后结果为$1$，必然与原来的$f$不相等。
算术逻辑单元
例题 $ALU$作为运算器的核心部件，其属于()。
$A.$时序逻辑电路
$B.$组合逻辑电路
$C.$控制器
$D.$寄存器
解：$B$。$ALU$是由组合逻辑电路构成的，最基本的部件是并行加法器。由于单纯的$ALU$不能够存储运算结果和中间变量，往往将$ALU$和寄存器或暂存器相连。