桂林景区网站建设策划方案,网站建设商城网站,wordpress小工具支持,网站开发的名称叫什么文章目录二进制数制十进制二进制位模式基本数据类型无符号数的编码有符号数的编码原码#xff08;Sign-Magnitude#xff09;反码#xff08;Ones Complement#xff09;补码#xff08;Twos Complement#xff09;概念导读编码格式按权展开补码加法扩展一个数字的位表示…
文章目录二进制数制十进制二进制位模式基本数据类型无符号数的编码有符号数的编码原码Sign-Magnitude反码Ones Complement补码Twos Complement概念导读编码格式按权展开补码加法扩展一个数字的位表示有符号数和无符号数之间的转换参考二进制数制
所谓数制是指计数的方法。
十进制
人两手加起来共10根手指故日常计数和做算术都使用十进制。大家熟悉并使用了一千多年的十进制起源于印度在12世纪被阿拉伯数学家改进并在13世纪被意大利数学家Leonardo PisanoFibonacci带到西方。1、2、3的罗马计数法是Ⅰ、Ⅱ、ⅢⅠⅡⅢ 直观展示了加法运算的含义。
数据无论使用哪种进位制都涉及两个基本要素基数radix与各数位的“位权”weight。 十进制数有两个特点
用0、1、2、3、…、9这10个基本符号表示基本数字符号数码的个数叫基数。遵循“逢十进一”原则每位计满十时向高位进一。
一般地任意一个十进制数 N 都可以表示为 ∑i−mn−1Ki∗10i\sum_{i-m}^{n-1}K_i\ast10^i∑i−mn−1Ki∗10i
NKn−1∗10n−1Kn−2∗10n−2⋯K1∗101K0∗100K−1∗10−1K−2∗10−2⋯K−m∗10−mN K_{n-1}\ast10^{n-1} K_{n-2}\ast10^{n-2} \cdots K_1\ast10^1 K_0\ast10^0 K_{-1}\ast10^{-1} K_{-2}\ast10^{-2} \cdots K_{-m}\ast10^{-m} NKn−1∗10n−1Kn−2∗10n−2⋯K1∗101K0∗100K−1∗10−1K−2∗10−2⋯K−m∗10−m
抛开小数部分整数按权的展开式为
N∑i0n−1Ki∗10iKn−1∗10n−1Kn−2∗10n−2⋯K1∗101K0∗100N \sum_{i0}^{n-1}K_i\ast10^i K_{n-1}\ast10^{n-1} K_{n-2}\ast10^{n-2} \cdots K_1\ast10^1 K_0\ast10^0 Ni0∑n−1Ki∗10iKn−1∗10n−1Kn−2∗10n−2⋯K1∗101K0∗100
一个数字符号在不同位时代表的数值不同。在上述表达式中数位 KiK_iKi 的权为 10i10^i10i以基数101010为底序号iii为指数数字符号乘以其位权为这个数字符号所表示的真实数值Ki∗10iK_i\ast10^iKi∗10i。
二进制
在 字节存储单元及struct内存分配 中我们介绍了二进制和以及字节存储单元。现代计算机存储和处理的信息以二值信号表示。这些微不足道的二进制数字或者称为位bit形成了数字革命的基础。
对于有10根手指的人来来说使用十进制表示法是很自然的事情但是当构造存储和处理信息的机器时二进制工作得更好。在计算机内部二进制总是存放在由具有两种相反状态的存储元件构成的寄存器或存储单元中即二进制数码0和1是由存储元件的两种相反状态来表示的。这使得二值信号很容易地被表示、存储和传输。
二值信号可以表示为导线上的高电压或低电压、晶体管的导通或截止、电子自旋的两个方向或者顺时针或逆时针的磁场。指令集及流水线 中提到在上个世纪的打孔编程时代纸带上的每个孔代表一位(bit)穿孔presence表示1未穿孔absence表示0这些孔序列被扫描识别为机器指令的二进制位串。
十进制数按权的展开式可以推广到任意进位计数制。二进制中只有0和1两个字符基数为2满足“逢二进一”。权用 2i2^i2i 表示二进制的按权展开式为 N∑i0n−1Ki∗2iN \sum_{i0}^{n-1}K_i\ast2^iN∑i0n−1Ki∗2i。
二进制与其他数制相比有以下显著特点
数制简单容易基于元器件的电子特性实现数字逻辑电路。由于二进制只有状态因此抗干扰性强可靠性、稳定性高。可以基于布尔逻辑代数进行分析和综合运算规则相对简单易实现。 基数为2的好处在于基本算术运算表很短对比一下十进制和二进制的加法和乘法表长短相形一目了然。 位模式
2个比特可以组合出4222^222种状态可表示无符号数值范围[0,3]32个比特可以组合出42949672962322^{32}232种状态可表示无符号数值范围[0,4294967295]……。
由于一个位只能表示二元数值所以单独一位的用处不大。当把位组合在一起再加上某种解释interpretasion即赋予不同的可能位模式以含意。通常将固定位数的位串作为一个基本存储单位这样就可以存储范围较大的值。在有限范围内的可计量数值几乎都可以用二进制数码位串组合表示计算机的内存由数以亿万计的比特位存储单元晶体管组成。
大多数计算机使用8位的块或者字节byte作为最小的可寻址的内存单位而不是访问内存中单独的位bit。机器级程序将内存视作一个非常大的字节数组内存的每个字节都由一个唯一的数字来标识称为它的地址。
每个程序对象可以简单地视为一个字节块程序本身本身就是一个字节序列机器指令序列。
基本数据类型
在 C Variable Types 中我们总结了C/C中的基本数据类型。C/C语言支持多种整形数据类型——表示有限范围的整数。每种类型都用关键字来指定大小这些关键字包括 char、short、long参考 gnu libc Integers。C/C语言都支持有符号默认和无符号数。
长短修饰符 short 和 long 用于修饰整形默认为 long 长整形短整形需显示指定 short。符号修饰符 signed 和 unsigned 用于修饰字符型和整形缺省为 signed 有符号类型无符号需显示指定 unsigned 修饰。当用 signed / unsigned、short / long 来修饰 int 整形时int 可省略。
以下是字符型、短整型、整型有无符号的区分表示
有符号字符型char/signed char无符号字符型unsigned char有符号短整型short [int] /signed short [int]无符号短整型unsigned short [int]有符号整型int /signed [int]无符号整型unsigned [int]
无符号数的编码
无符号unsigned编码基于传统的二进制表示法表示大于或等于0的非负数。
假设有一个整数数据类型有 nnn 位。我们可以将位向量写成 x⃗\vec{x}x 表示整个向量或者写成 [xn−1,xn−2,⋯,x0][x_{n-1}, x_{n-2}, \cdots, x_0][xn−1,xn−2,⋯,x0]表示向量中的每一位。把 x⃗\vec{x}x 看成一个二进制表示的数就获得了 x⃗\vec{x}x 的无符号表示。在这个二进制编码中每个位 xix_ixi 都取值0或1后一种取值意味着数值 2i2^i2i 应为数字值的一部分。我们用一个函数 B2UnB2U_nB2UnBinary to Unsigned的缩写长度为nnn来表示。
对位向量 x⃗[xn−1,xn−2,⋯,x0]\vec{x} [x_{n-1}, x_{n-2}, \cdots, x_0]x[xn−1,xn−2,⋯,x0]
B2Un(x⃗)˙∑i0n−1xi∗2iB2U_n(\vec{x}) \dot\sum_{i0}^{n-1}x_i\ast2^i B2Un(x)˙i0∑n−1xi∗2i
在这个等式中等号“˙\dot˙”表示左边被定义为等于右边。函数 B2UnB2U_nB2Un 将一个长度为 nnn 的0、1串映射到非负整数。
nnn 位所能表示的最小值用位向量[00⋯0][00\cdots0][00⋯0]全零表示也就是整数值0而最大值是用位向量[11⋯1][11\cdots1][11⋯1]全1也就是整数值 UMaxw˙∑i0n−1xi∗2i2n−1UMax_w\dot\sum_{i0}^{n-1}x_i\ast2^i2^n-1UMaxw˙∑i0n−1xi∗2i2n−1。即nnn位二进制位串所能表示的数值范围是 [0,2n−1][0, 2^n-1][0,2n−1]。
在主流64位LP64架构实现中unsigned char、unsigned short [int]、unsigned [int]、unsigned long [int]或 long unsigned [int]分别占1、2、4、8个字节8、16、32、64位。无符号字符unsigned char占用1个字节8位所能表示的数值范围是 [0,28−1][0,255][0, 2^8-1] [0, 255][0,28−1][0,255]。
有符号数的编码
对于很多应用我们还希望表示负数值。在计算机中如何表示符号呢 在计算机中对于数的符号正号和负号-也只能用0和1这两位数字表示。通常用一个数的最高位作为符号位最高位为0表示符号位为正最高位为1表示符号位为负。这样数的符号标识也“数码化”了。即带符号数的数值和符号统一用二进制数码形式来表示。
在将数的符号用数码0或1表示后数值部分究竟是保留原来的形式还是按一定的规则做某些变化这要取决于运算方法的需要从而有四种常见的机器数形式原码、反码、补码 和 移码。
为了区别原来的数与它在机器中的表示形式将一个数连同符号在机器中加以数码化后的形式称为机器数或机器码而把机器数所代表的实际数值称为真值。
原码Sign-Magnitude
原码表示法比较直观其数值部分保留其真值的绝对值。
8位二进制原码表示的数值范围为 11111111-10000000,00000000-01111111即 -127 - -0,0 - 127。其中“0”有-0和0之分[−0]原10000000[-0]_原1 0000000[−0]原10000000[0]原00000000[0]_原0 0000000[0]原00000000。
例如正数89的二进制表示为 101100110110011011001其原码表示为 负数-89的二进制表示为 −1011001-1011001−1011001其原码表示为 原码表示法的优点是比较直观、简单易懂后面在浮点数中有使用到原码编码。 原码的符号位不是数值的一部分不能直接参与运算导致加法运算复杂。 为了解决这些矛盾人们引入了反码和补码。 反码Ones’ Complement
对于正数而言其反码形式与其原码相同最高位为符号位用0表示正数其余位为数值位不变。对于负数而言其反码表示为最高位符号位为1其余数值位在原码的基础上按位取反。反码在机器中的表示形式如下
8位二进制反码表示的数值范围为 10000000-11111111,00000000-01111111负数数值部分求反复原11111111-10000000,00000000-01111111即 -127 - -0,0 - 127。其中“0”有-0和0之分[−0]反11111111[-0]_反1 1111111[−0]反11111111[0]反00000000[0]_反0 0000000[0]反00000000。
-89的二进制表示为 −1011001-1011001−1011001其原码表示为 110110011 101100111011001则其反码表示为 101001101 010011010100110。 将反码表示规则用表达式形式定义如下
[X]反{X,X0或X0(2n−1)−∣X∣(2n−1)X,X0或X−0% 反码 [X]_反 \begin{cases} X, X0 或 X0 \\ (2^n-1)- \lvert X \rvert(2^n-1) X, X0 或 X-0 \end{cases} [X]反{X,(2n−1)−∣X∣(2n−1)X,X0或X0X0或X−0
当 X0 或 X-0 时按照无符号数解析位向量∣X∣[X]反→2n−1\lvert X \rvert \overrightarrow{[X]_反}2^n-1∣X∣[X]反2n−1。例如当n8时∣X∣[X]反→11111111255\lvert X \rvert \overrightarrow{[X]_反}11111111255∣X∣[X]反11111111255。 虽然过去生产过基于反码表示的机器但是几乎所有的现代机器都使用补码形式表示有符号整数。 现在通常已不再单独使用反码而主要是作为求补码的一个中间步骤来使用。 补码Two’s Complement
在计算机中最常见的有符号整数的表示方式是补码。采用补码运算可以将减法变成补码加法运算在微处理器中只需加法的电路就可以实现加法、减法运算。
概念导读
为了理解补码的概念我们先来看看圆周运动的例子。
在现实生活中一个圆周的可视角度度量为0-2π或0°-360°以原点为起点的射线OA逆时针旋转一圈的弧度为2π。
圆周运动具有周期性即具有“周而复始”的变化规律。假设OA的初始弧度为α终边OA每绕原点旋转一周α增加2π弧度旋转k周后弧度变成αk·2π但OA位置不变。由三角函数的定义可知终边相同的角的同一三角函数的值相等。
sin(αk⋅2π)sinαcos(αk⋅2π)cosαtan(αk⋅2π)tanα\begin{gather*} \sin(\alphak·2\pi) \sin\alpha \\ \cos(\alphak·2\pi) \cos\alpha \\ \tan(\alphak·2\pi) \tan\alpha \end{gather*} sin(αk⋅2π)sinαcos(αk⋅2π)cosαtan(αk⋅2π)tanα
由上面的公式可知可以把求任意角的三角函数值转化为求0-2π或0°-360°角的三角函数值。射线OA逆时针旋转π和顺时针旋转π-π的终边是相同的逆时针旋转5π/3和顺时针旋转π/3-π/3的终边是相同的。以下将负弧度的正弦计算转化到0-2π区间换算
sin(−π2π)sinπsin(−π32π)sin5π3\begin{gather*} \sin(-\pi2\pi) \sin\pi \\ \sin(-\frac{\pi}{3}2\pi) \sin\frac{5\pi}{3} \end{gather*} sin(−π2π)sinπsin(−3π2π)sin35π 我们再来进一步看看日常生活中校正时钟的例子。
假定时钟停在7点而正确时间是5点要拨准时钟可以有两种不同的拨法倒拨2个格或顺拨10个格。
想象一下龟兔在7点钟刻度背向而行假设兔子的速度是乌龟的5倍兔子顺时针跑10格乌龟逆时针跑2格它们将在5点刻度处迎面相遇。
由于钟面的容量有限其表盘刻度实际上是十二进制12h以后又从0开始计数。倒拨2个格即7-25做减法顺拨10个格即710125做加法。而钟面上120故125回归到刻度5。这就表明在舍掉进位的情况下“从7减去2”和“往7加上10”所得的结果是一样的。在十二进制下125丢失进位12此处12是溢出量又称为模mod。而2和10的和恰好等于模数12我们把10称为-2对于模数12的补数。在圆周运动中每转动一周的2π弧度可视为溢出量模5π/3为-π/3对于模数2π的补数。
在电脑和手机的日期和时间偏好设置中通常可以设置显示24小时因为地球自转一圈是一天接近24h。24h制的1点和13点都对应钟表上的1点。“天天向上”、“日复一日”中的“天”和“日”即为溢出量每过24h模又将开启崭新的一天。
计算机中的运算受一定字长的限制它的运算部件、寄存器和存储单元都有一定的位数因而在运算过程中也会产生溢出量所产生的溢出量实际上就是模。可见计算机的运算也是一种有模运算。
编码格式
对于正数而言其补码形式与其原码、反码相同最高位为符号位用0表示正数其余位为数值位不变。对于负数而言其补码表示为最高位符号位为1其余数值位在原码的基础上按位取反并加1反码1。补码在机器中的表示形式如下 -89的二进制表示为 −1011001-1011001−1011001其原码表示为 110110011 101100111011001其反码表示为 101001101 010011010100110则其补码表示为 101001111 010011110100111。
8位二进制补码表示的数值范围为 10000000-11111111,00000000-01111111即 -128 - -1,0 - 127。其中无-0和0之分保证了0的唯一性。另外取值范围为连贯区间 [-128, 127]包含128个负数、128个非负数。负数、非负数各占一半负数比正数多一个。
将补码表示规则用表达式形式定义如下
[X]补{X,X≥02n−∣X∣2nX,X0% 补码 [X]_补 \begin{cases} X, X\ge0 \\ 2^n- \lvert X \rvert2^nX, X0 \end{cases} [X]补{X,2n−∣X∣2nX,X≥0X0
当 X0 时按照无符号数解析位向量∣X∣[X]补→2n\lvert X \rvert\overrightarrow{[X]_补}2^n∣X∣[X]补2n。例如当n8时∣X∣[X]补→111111111256\lvert X \rvert\overrightarrow{[X]_补}111111111256∣X∣[X]补111111111256。
-89的二进制补码表示为 101001111 010011110100111按照无符号数解析位向量的值为167满足以下
∣−89∣167256256(−89)167\begin{aligned} \lvert -89 \rvert 167 256 \\ 256(-89) 167 \end{aligned} ∣−89∣167256256(−89)167
按权展开
-89的二进制表示为 −1011001-1011001−1011001其原码表示为 110110011 101100111011001其反码表示为 101001101 010011010100110则其补码表示为 101001111 010011110100111。
∣−89∣\lvert -89 \rvert∣−89∣ 的二进制位向量为 010110010101100101011001
反码数值部分位向量(2n−1−1)−∣X∣127−∣−89∣0b01111111−0b010110010b00100110(2^{n-1}-1)-\lvert X \rvert 127-\lvert -89 \rvert0b01111111-0b010110010b00100110(2n−1−1)−∣X∣127−∣−89∣0b01111111−0b010110010b00100110。补码数值部分位向量(2n−1−1)−∣X∣12n−1−∣X∣127−∣−89∣10b01111111−0b0101100110b00100111(2^{n-1}-1)-\lvert X \rvert1 2^{n-1}-\lvert X \rvert 127-\lvert -89 \rvert10b01111111-0b0101100110b00100111(2n−1−1)−∣X∣12n−1−∣X∣127−∣−89∣10b01111111−0b0101100110b00100111。
补码高位符号位占1位其余数值部分占 n-1 位。当将最高符号位解释为负权2n−12^{n-1}2n−1时整体位向量刚好可计算出原始负值
−2n−1(2n−1−∣X∣)−∣X∣-2^{n-1} (2^{n-1}-\lvert X \rvert) -\lvert X \rvert −2n−1(2n−1−∣X∣)−∣X∣
我们用一个函数 B2TwB2T_wB2TwBinary to Two’s Complement 的缩写长度为www来表示位向量 x⃗[xn−1,xn−2,⋯,x0]\vec{x} [x_{n-1}, x_{n-2}, \cdots, x_0]x[xn−1,xn−2,⋯,x0] 到补码的编码映射
B2Tn(x⃗)˙−xn−1∗2n−1∑i0n−2xi∗2iB2T_n(\vec{x}) \dot-x_{n-1}\ast2^{n-1} \sum_{i0}^{n-2}x_i\ast2^i B2Tn(x)˙−xn−1∗2n−1i0∑n−2xi∗2i
最高有效位 xn−1x_{n-1}xn−1 称为符号位它的“权重”为 −2n−1-2^{n-1}−2n−1是无符号表示中权重的负数。符号位被设置为1时表示值为负而当设置为0时值为非负。
∣−89∣\lvert -89 \rvert∣−89∣ 的二进制位向量为 010110010101100101011001-89的二进制补码表示为 101001111 010011110100111可基于 B2TnB2T_nB2Tn 函数按权展开复原补码的真值
B2T8([01011001])−0∗271∗261∗241∗231∗20−064168189B2T8([10100111])−1∗271∗251∗221∗211∗20−12832421−89\begin{aligned} B2T_8([0 1011001]) -0\ast2^71\ast2^61\ast2^41\ast2^31\ast2^0-064168189 \\ B2T_8([1 0100111]) -1\ast2^71\ast2^51\ast2^21\ast2^11\ast2^0-12832421-89 \end{aligned} B2T8([01011001])−0∗271∗261∗241∗231∗20−064168189B2T8([10100111])−1∗271∗251∗221∗211∗20−12832421−89
让我们基于 B2TnB2T_nB2Tn 展开式重新推导一下 nnn 位补码所能表示的取值范围。
最小值是位向量 [10⋯0][10\cdots0][10⋯0]只设置负权其他正权位清零此种情形负得最多其整数值为 TMinn˙−2n−1TMin_{n}\dot-2^{n-1}TMinn˙−2n−1。当设置了负权时设置其他所有正权位位向量为 [11⋯1][11\cdots1][11⋯1]。此种情形正权打满负得最少其整数值为 −2n−1∑i0n−2xi∗2i−2n−1(2n−1−1)−1-2^{n-1}\sum_{i0}^{n-2}x_i\ast2^i-2^{n-1}(2^{n-1}-1)-1−2n−1∑i0n−2xi∗2i−2n−1(2n−1−1)−1即最大负整数。最大值是位向量 [01⋯1][01\cdots1][01⋯1]清除负权即为非负数清除其他所有正权位其值为0若设置其他所有正权位其整数值为 TMaxn˙∑i0n−2xi∗2i2n−1−1TMax_{n}\dot\sum_{i0}^{n-2}x_i\ast2^i2^{n-1}-1TMaxn˙∑i0n−2xi∗2i2n−1−1。
以n8n8n8为例一个字节byte的补码编码所能表示数值范围是 [−28−1,28−1−1][-2^{8-1}, 2^{8-1}-1][−28−1,28−1−1]即 [−128,127][-128, 127][−128,127]包含128个负数-128 - -1、128个非负数0 - 127。
补码加法
计算机的表示法使用有限数量的位对一个数字编码当结果太大以至不能表示时某些运算就会溢出overflow。因此我们说计算机运算也是一种有模运算。当然在计算机中不是像上述时钟例子那样以12为模在定点小数的补码表示中是以 222 为模在定点整数中则以 2n2^n2n 为模n8,16,32,64,…。
计算机中用补码表示法编码有符号数把负数用补码表示。减去一个正数可以看成加上一个负数这样在计算机中不用单独设置减法器而是基于补码一律按加法运算规则实现减法的等效计算。
回想调拨钟表的例子2和10的和恰好等于模数12我们把10称为-2对于mod12的补数。其含义是在钟表盘上逆时针回拨2格等效于顺时针拨动10格。
【例1】已知X00001117Y-0010011-19求两数的补码之和。
[X]补00000111[Y]补11101101[X]_补0 0000111[Y]_补1 1101101[X]补00000111[Y]补11101101人工计算 ZXY7(-19)-12补码为11110100。
若将 [Y]补→\overrightarrow{[Y]_补}[Y]补 也视作无符号数237将计算结果Z也直视为无符号数[Z]补→\overrightarrow{[Z]_补}[Z]补244满足 7237244。244恰为-12对于mod256的补数。
设想一个有256个刻度的大笨钟初始在刻度7点处逆时针回拨19格和顺时针拨动237格效果都是拨到刻度244处。当采用补码表示时表盘的256个刻度被重新编码划分成左边逆时针半盘[-128,-1]和右边顺时针半盘[0,127]原先的244点映射为新刻度下左半盘的-12点位。换个角度来看由于 ∣−19∣∣7∣\lvert -19 \rvert \gt \lvert 7 \rvert∣−19∣∣7∣这里的异号相加负数占主导也可以想象初始刻度左半盘-19点7表示顺时针拨动7格将拨到-12点仍然在左半盘没有溢出。
在钟表盘刻度范围内逆时针的减法和顺时针的加法加减量互补最终达到同一刻度点。在模数例如mod256范围内减法可以视作加补码计算反码本身已经做了减法运算补码可以视作无符号数直接参与竖式按位加计算。另一方面由于操作数和运算结果都统一用补码表示补码的最高符号位统一按照负权解释即补码的符号位可视作整体数值的一部分。从这个角度讲符号位直接参与运算貌似也是解释得通。
接下来我们重点看看补码加法的溢出问题及溢出判断。
【例2】已知X100000064Y100000165求两数的补码之和。
直接对补码列竖式计算如下
01(CfC0)[X]补01000000(64的补码))[Y]补01000001(65的补码)10000001129\begin{array}{c|lcr} \:\:\:\:\: \: \quad 0\ 1 \qquad\qquad\qquad (C_fC_0)\\ \:\:\:\:\: [X]_补 \qquad 0\ 1000000 \qquad (64的补码) \\ ) [Y]_补 \qquad 0\ 1000001 \qquad (65的补码) \\ \hline \ \qquad 1\ 0000001 \qquad 129 \end{array} [X]补)[Y]补 0 1(CfC0)0 1000000(64的补码)0 1000001(65的补码)1 0000001129
两个正数相加结果为负数补码之和是129超出了 [0, 127]即产生了溢出现象。此时数值部分向符号位产生进位C01C_01C01符号位未向高位产生进位 Cf0C_f0Cf0。
这里两个正数相加结果超出了8位补码的非负数表示范围溢出到了负数区。还是借用256大笨钟来阐述初始在刻度65点处顺时针拨动64格将到129点。但是当采用补码表示时129点越过右半盘取值范围为[0,127]的分界线127点两格落入了左半盘取值范围为[-128,-1]的-127点位127左溢一格是-128再左溢一格是-127。
用以下C语言代码测试验证计算结果Z的位向量为0x81即无符号数129补码对应的真值-127。 signed char X 64;signed char Y 65;signed char Z XY;printf(Z0x%hhx, %hhd\n, Z, Z);【例3】已知X-1111111-127Y-0000010-2要求进行补码的加法运算。
直接对补码列竖式计算如下
10(CfC0)[X]补10000001(−127的补码))[Y]补11111110(−2的补码254)01111111127\begin{array}{c|lcr} \:\:\:\:\: \: \quad 1\ 0 \qquad\qquad\qquad (C_fC_0)\\ \:\:\:\:\: [X]_补 \qquad 1\ 0000001 \qquad (-127的补码) \\ ) [Y]_补 \qquad 1\ 1111110 \qquad (-2的补码254) \\ \hline \ \qquad 0\ 1111111 \qquad 127 \end{array} [X]补)[Y]补 1 0(CfC0)1 0000001(−127的补码)1 1111110(−2的补码254)0 1111111127
两个负数相加结果为正数预期的结果-129超出了8位补码所能表示的负数范围 [-128, -1]即产生了溢出现象。此时数值部分向符号位未产生进位 C00C_00C00符号位向高位产生进位 Cf1C_f1Cf1。
这里两个负数相加结果超出了8位补码的负数表示范围溢出到了正数区。由于 ∣−127∣∣−2∣\lvert -127 \rvert \gt \lvert -2 \rvert∣−127∣∣−2∣这里的负负相加-127占主导。还是借用256大笨钟来阐述当采用补码表示时想象初始刻度左半盘-127点处-2表示逆时针拨动2格越过左半盘分界线-128点一格落入了右半盘取值范围为[0,127]的127点位-127右溢一格是-128再右溢一格是127。
用以下C语言代码测试验证计算结果Z的位向量为0x7f符号位溢出为0补码对应的真值即无符号值127。 signed char X -127;signed char Y -2;signed char Z XY;printf(Z0x%hhx, %hhd\n, Z, Z);【例4】已知X-0000011-3Y-0000010-2要求进行补码的加法运算。
直接对补码列竖式计算如下
11(CfC0)[X]补11111101(−3的补码253))[Y]补11111110(−2的补码254)11111011(−5的补码251)\begin{array}{c|lcr} \:\:\:\:\: \: \quad 1\ 1 \qquad\qquad\qquad (C_fC_0)\\ \:\:\:\:\: [X]_补 \qquad 1\ 1111101 \qquad (-3的补码253) \\ ) [Y]_补 \qquad 1\ 1111110 \qquad (-2的补码254) \\ \hline \ \qquad 1\ 1111011 \qquad (-5的补码251) \end{array} [X]补)[Y]补 1 1(CfC0)1 1111101(−3的补码253)1 1111110(−2的补码254)1 1111011(−5的补码251)
直接补码运算产生的结果的无符号数值是251正是预期结果-5的补码此时数值部分向符号位产生进位 C01C_01C01符号位向高位产生进位 Cf1C_f1Cf1未溢出。 以上例1和例4中8位正数之和、8位负数之和未超出8位补码表示的数值范围时没有产生溢出结果正确。此时满足 C0CfC_0C_fC0Cf同时为0或同时为1。 以上例2和例3中8位正数之和、8位负数之和超出8位补码表示的数值范围时产生了溢出结果错误。此时满足 C0≠CfC_0 \ne C_fC0Cf一个为0且一个为1。
综合以上可用下列逻辑表达式进行补码加法的溢出判断
OFCf⊕C0OF C_f \oplus C_0 OFCf⊕C0
扩展一个数字的位表示
一个常见的运算是在不同字长的整数之间转换同时又保持数值不变。考虑从一个较小的数据类型转换到一个较大的类型即扩大位宽。
要将一个无符号数转换成一个更大的数据类型时只要简单地在开头添加0。具体来说原数值的字节保持在低权位不变在新增的高权位补0。
要将一个补码数字转换为一个更大的数据类型可以执行一个符号扩展sign extension。具体来说原数值的字节保持在低权位不变在新增的高权位复制符号位。
对于正数高位复制符号位0不影响其真值。对于负数高位复制符号位1也不影响真值。
考虑负数的补码位向量 x⃗[xw−1,xw−2,⋯,x0]\vec{x} [x_{w-1}, x_{w-2}, \cdots, x_0]x[xw−1,xw−2,⋯,x0]其编码映射如下
B2Tw(x⃗)˙−xw−1∗2w−1∑i0w−2xi∗2iB2T_w(\vec{x}) \dot-x_{w-1}\ast2^{w-1} \sum_{i0}^{w-2}x_i\ast2^i B2Tw(x)˙−xw−1∗2w−1i0∑w−2xi∗2i
当复制高符号位 xw−1x_{w-1}xw−1 时位向量 x′⃗[xw−1,⋯,xw−1,xw−1,xw−2,⋯,x0]\vec{x} [x_{w-1}, \cdots, x_{w-1}, x_{w-1}, x_{w-2}, \cdots, x_0]x′[xw−1,⋯,xw−1,xw−1,xw−2,⋯,x0]则有 B2Tw(x⃗)B2Tw′(x′⃗)B2T_w(\vec{x}) B2T_{w}(\vec{x})B2Tw(x)B2Tw′(x′)。 以-89为例其8位补码位向量为[10100111][1 0100111][10100111]将其符号扩展为16位的位向量位[1111111110100111][11111111 10100111][1111111110100111]
B2T8([10100111])−1∗271∗251∗221∗211∗20−12832421−89B2T16([1111111110100111])−1∗2151∗214⋯1∗281∗271∗251∗221∗211∗20−12832421−89\begin{aligned} B2T_8([1 0100111]) -1\ast2^71\ast2^51\ast2^21\ast2^11\ast2^0-12832421-89 \\ B2T_{16}([11111111 10100111]) -1\ast2^{15}1\ast2^{14}\cdots1\ast2^81\ast2^71\ast2^51\ast2^21\ast2^11\ast2^0-12832421-89 \end{aligned} B2T8([10100111])−1∗271∗251∗221∗211∗20−12832421−89B2T16([1111111110100111])−1∗2151∗214⋯1∗281∗271∗251∗221∗211∗20−12832421−89
我们设补码除符号位后的数值位值为v则
B2T8([10100111])−1∗27vB2T16([1111111110100111])−1∗2151∗214⋯1∗281∗27v\begin{aligned} B2T_8([1 0100111]) -1\ast2^7v \\ B2T_{16}([11111111 10100111]) -1\ast2^{15}1\ast2^{14}\cdots1\ast2^81\ast2^7v \end{aligned} B2T8([10100111])−1∗27vB2T16([1111111110100111])−1∗2151∗214⋯1∗281∗27v
更进一步有
B2T16([1111111110100111])28(−2726⋯20)27v28(−27(27−1))27v−2827v−27v\begin{aligned} B2T_{16}([11111111 10100111]) 2^8(-2^72^6\cdots2^0)2^7v \\ 2^8(-2^7(2^7-1))2^7v \\ -2^82^7v \\ -2^7v \end{aligned} B2T16([1111111110100111])28(−2726⋯20)27v28(−27(27−1))27v−2827v−27v
对比可知符号扩展前后的补码所表示的真值不变。
有符号数和无符号数之间的转换
C语言允许在各种不同的数据类型之间做强制类型转换。例如假设变量x声明为intu声明为unsigned。表达式 (unsigned)x 会将x的值转换为一个无符号数值而 (int)u 将u的值转换为一个有符号整数。
考虑以下代码 short int v -12345;unsigned short uv (unsigned short)v;printf(v%hd, uv%hu\n, v, uv);printf(v0x%hx, uv0x%hx\n, v, uv);在一台采用补码的机器上上述代码运行输出
v-12345, uv53191
v0xcfc7, uv0xcfc7可以看到强制类型转换的结果保持位向量位模组不变只是改变了解释这些位的方式。 v-12345 的补码表示和 uv53191 的无符号表示是完全一样的。
以上代码片段示例演示了负数补码转换成无符号数。对于负数补码中最高位作为符号位本来解释为负权 −2w−1-2^{w-1}−2w−1按照无符号解释为正权数值位 2w−12^{w-1}2w−1。由于后面位的数值 vvv 保持不变相当于在补码表示的真值基础上加上 2w2^w2w。
对满足 TMinw≤x≤TMaxwTMin_w \le x \le TMax_wTMinw≤x≤TMaxw 的 xxx 有
T2Uw(x){x,x≥02wx2w−∣x∣,x0T2U_w(x) \begin{cases} x, x\ge0 \\ 2^wx2^w- \lvert x \rvert, x0 \end{cases} T2Uw(x){x,2wx2w−∣x∣,x≥0x0
简单推导如下
B2Uw(x)−B2Tw(x)(2w−1v)−(−2w−1v)2∗2w−12w⟹B2Uw(x)B2Tw(x)2w\begin{aligned} B2U_w(x) - B2T_w(x) (2^{w-1}v)-(-2^{w-1}v) 2\ast2^{w-1}2^w \\ \implies B2U_w(x) B2T_w(x) 2^w \end{aligned} B2Uw(x)−B2Tw(x)(2w−1v)−(−2w−1v)2∗2w−12w⟹B2Uw(x)B2Tw(x)2w
例如T2U16(−12345)−1234521653191T2U_{16}(-12345) -123452^{16}53191T2U16(−12345)−1234521653191。 同理无符号数的最高位解释为正权数值位 2w−12^{w-1}2w−1当将其位向量解释成补码时最高位将作为符号位解释为负权 −2w−1-2^{w-1}−2w−1。由于后面位的数值 vvv 保持不变相当于在无符号真值基础上减去 2w2^w2w。
对满足 0≤u≤UMaxw0 \le u \le UMax_w0≤u≤UMaxw 的 uuu 有
U2Tw(u){u,u≤TMaxwu−2w,uTMaxwU2T_w(u) \begin{cases} u, u \le TMax_w \\ u - 2^w, uTMax_w \end{cases} U2Tw(u){u,u−2w,u≤TMaxwuTMaxw
对于 w8w8w8当 u≤TMaxw127u \le TMax_w 127u≤TMaxw127 时即 0≤u≤1270 \le u \le 1270≤u≤127刚好落入8位补码所能表示的非负数区间 当 uTMaxw127u \gt TMax_w 127uTMaxw127 时例如 128≤u≤255128 \le u \le 255128≤u≤255则原始高位1变成负号补码释义为负数。原来位向量按无符号解释出的真值需减去 282562^825628256换算出按补码解释的正确真值对应负数区间 [−1,−128][-1, -128][−1,−128]。
我们在数轴上把有符号数和无符号数画出来的话就能很清晰的看出相对的关系
参考
《深入理解计算机系统》第3版 《计算机组成原理》第3版唐朔飞 《微机原理与接口技术》第2版王克义 《汇编语言程序设计》第4版文全刚
深入谈谈二进制 补码表示法的本质原理 【读薄 CSAPP】壹 数据表示 从晶体管开始聊聊计算机为什么采用二进制
