二进制:有符号整数编码和加减运算
简介
在计算机上,数字编码和字符编码本质上都通过二进制来编码。但数字二进制编码除了存储功能,还要求具备运算功能。这也就意味着它会和硬件计算单元有非常紧密的关系。
对于一个 8 bit 大小的存储,二进制的 0 和 1 有 种组合。如果为自然数编码,能为 [0,...,255] 一共 256 个自然数的编码,最大的那个数字是:。
如果你高兴,可以随意一个数字开始编码。比如:从 103 开始编码,能为 [103,...,358] 一共 256 个数字编码,最大的那个数字是:。
如果在 8 bit 大小的存储中,把负整数
也编码进来,常用的做法是各自分一半的编码数。也就是说负整数占 128 个,正整数占 128 个。那么他们的数值范围可以是负整数区 [-128,...,-1] 和正整数区 [1,...,128]。显然,少了对 0 的编码。为了把 0 也编入。把正整数区的改为从 0 开始的编码。
于是有符号的 8 位整数的数值范围是 [-128,...,-1,0,1,...,127],即 。以此类推:
- 16 位可以表示范围值:。
- 32 位可以表示范围值:。
- 64 位可以表示范围值:。
在计算机中,所有的数据都是以二进制形式存储的。我们通过除 2 倒取余
和按权相加
方法对二进制数和十进制数之进行互转:
有符号整数的编码
在给定位数的情况下,它所能表示的编码个数是确定的。8 位的编码个数是 , 16 位则是 个。所以剩下的问题就是如何对数值范围里的数值分配二进制编码。
从计算机发展历史来看有三种编码方式:原码
(Sign-Magnitude)、反码
(One's Complement) 和补码
(Two's Complement)。
IBM 是原码
(Sign-Magnitude) 的早期支持者之一,其 704、709 和 709x 系列计算机可能是最著名的使用原码的系统。
反码
(One's Complement) 这种数字表示系统通常出现在老式的计算机中;PDP-1,CDC 160A,UNIVAC 1100/2200 系列。Internet 协议 IPv4
,ICMP
,UDP
以及 TCP
都使用同样的 16 位反码检验和
算法。
补码
(Two's Complement) 是目前事实上的数字编码标准,被广泛使用。
这三种编码方式的不同点是对负数
的编码,而正数的编码和数学里的二进制数字表示系统一样。
原码
原码
(Sign-Magnitude) 把整数分成两部分:符号位
(Sign Bit) 和数值
(Magnitude)。
-
符号位
是二进制的最高位 (最左边),表示整数的正负
号。0
表示正整数
,1
表示负整数
。 -
数值
表示整数的绝对值
。
对于一个 8 位的十进制数 100 和 -100,其原码如下图所示:
反码
反码
(One's Complement) 或者一的补码
的表示系统的操作如下:
-
正数
和原码的正数表示方式一样。 -
负数
的编码操作是对正数按位取反
即可获得,1
逻辑非 (NOT) 为0
,0
逻辑非为·
。
对于一个 8 位的十进制数 100 和 -100,其反码如下图所示:
反码
引入了数字补码
(Numeric Complements)。在应用上,使用(基数 - 1) 的补码策略
,二进制系统的基数是 2,所以叫一的补码
。
反码这个翻译,目前只有内地教科在用。港台地区翻译采用直译叫
一补码
或一补数
。同时,补码和补数都是 Complement 的翻译。
如十进制系统,以 10 为基数,使用 (基数 - 1) 的补码策略叫九的补码
。对于一的补码
和九的补码
,我们可以统称为减基数补码
。
使用补码的好处可以统一加减法逻辑电路,即使用加法电路执行减法运算,这会节约硬件成本。
数字补码系统没有特意指定符号位,
不过,反码和原码对 0 的编码都多出了一个。比如在一个 4 位大小的二进制系统下:
- 原码对 0 的编码为 [0000] 和 [1000]。
- 反码对 0 的编码为 [0000] 和 [1111]。
因为对 0 的重复编码,导致最终数值范围会少一个。8 位存储大小,使用反码技术对有符号整数表示数值范围是 。由于存在两种表示零的方式,程序员和硬件设计者就需要考虑这一点,以避免可能的错误和混淆。
同时,每次加减法运算更为复杂。如加法的结果产生了进位,这个进位需要加回到结果的最低位,这称为端点进位
。
补码
补码
(Two's Complement) 或者二的补码
是最常见的有符号整数编码方式,它是现代计算机系统中,表示有符号整数的标准方法
。它的表示系统的操作如下:
-
正数
和原码的正数表示方式一样。 -
负数
的编码操作是对正数按位取反
之后,再加 1
。
对于一个 8 位的十进制数 100 和 -100,其补码如下图所示:
补码
(Two's Complement) 同样使用数字补码,不过在应用上使用基数补码
(Radix Complement)的策略。因此也叫二的补码
。
如果是十进制系统,以 10 为基数,使用基数的补码策略叫十的补码
。对于二的补码
和十的补码
,我们可以统称为基数补码
。
二补码改进了一补码的加法运算,并且对 0 的编码只有一个。
深入理解
上面介绍了三种二进制数的编码的表示方式,但没有讨论具体为什么这么去编码,以及为什么补码成为了计算机事实上的有符号整数的编码标准。
下面会介绍一些其它概念,来描述计算机运算的基本规律,从而了解补码的应用。
模算术
在数学中,模算术 (Modular arithmetic) 是一种整数算术
系统,其中数字在达到某个值
时进行“环绕”,该值称为模
(modulus) 。现代模算术方法是由卡尔·弗里德里希·高斯
(Carl Friedrich Gauss) 在其 1801 年出版的《算术研究》一书中提出的,包括同余的概念。模算术是很基础的理论,但厉害的是应用学科非常广泛。
模
(modulus) 是指一个计量系统的计数范围,如过去计量粮食用的斗
、时钟
等。计算机也可以看成一个计量机器,因为计算机的字长
是定长的
,即存储和处理的位数是有限的,因此它也有一个计量范围。
如:时钟
的计量范围是 ,模
= 。表示 位的计算机计量范围是 ,模 = 。任何有模的计量器,均可化减法为加法
运算。
假设当前时针指向 8 点,要调成 6 点,调整方式可以通过倒拨 2 小时
或顺拨 10 小时
来实现。
在 12 为模的系统里,加 10
和减 2
效果是一样的,因此凡是减 2 运算,都可以用加 10 来代替。对“模”而言,2 和 10 互为补数
(Complement)。实际上,以 12 为模的系统中,11 和 1,8 和 4,9 和 3,7 和 5,6 和 6 都有这个特性,共同的特点是两者相加等于模
。
在时钟这样的模运算系统
中,8 - 2 的运算操作结果值等于 8 + 10,可以记作 (8 + 10) mod 12。编程里 mod 通常使用 %
符号,表示取余
。因此,8 - 2 = (8 + 10) % 12 = 6,并且可以看到它们还具备 的关系。在数论中,称 -2 和 10 是对模 12 的同余关系。
计算机运算系统也是一个模运算模型
在计算机里,如果计算结果 > 最大表示数值,最高位就会进位。因为没有可以存储最高位进位值的地方,所以产生了溢出
,也就是进位溢出
。
如给定一个 8 位 (bit) 大小的存储单元,在为 的范围数值编码情况时下,进行 的计算,最高就会进位溢出,计算结果又回到 ,也就是数值 0,这样形成了和时钟一样的循环计数功能。
二进制减法变加法
我们来看看二进制的减法运算如何变成加法的。
当有限位数的计数器执行加法时,产生了进位溢出,溢出的部分就是模,它被自然抛弃,剩下部分就是减法的结果值 3。
同时,我们也可以看出减数 2
和模算术系统的加数
之间互为补码
,也就意味着我们模算术系统的加数
直接通过 模 - 2
,即 16 - 2 = 14 获取。
计算机引进补码可以把减法变加法,统一使用加法逻辑电路,来简化硬件设计。编译器对减数的补码计算实际比手工计算简单很多,也就是上面按位取反 + 1
操作,并且每一位的取反操作在电路上是并行操作。下面的章节会解释为什么按位取反 + 1
的结果就是补码
(Two's Complement)。
补码的计算
通过模,已经引出了补码 (Complement) 的概念,而在此基础上建立了更为广泛的数字补码
(Numeric Complements),其中在进制系统中,基数补码和减基数补码较为常见。
基数补码
(Radix Complement) 与某个基数 (radix) 的幂
有关。在这样的系统中,一个数
和它的补码相加
会得到它的模
,其中 是基数
, 是位数
。即 。
在一个 位十进制系统中:。
在一个 位二进制系统中:。
求 r 补码公式如下:
- 是数字中的位数。
- 为已给出的整数。
- 是基数(进制)。
除了基数补码外,还有一种补码方式,就是基数 - 1
的补码方式,也就是减基数补码
(Diminished Radix Complement)。
在十进制数制中,基数补码称为十的补码
,减基数补码
称为九的补码
。而在二进制中,基数补码称为二的补码
(补码),减基数补码
称为一的补码
(反码)。
有些人,特别是 Donald Knuth,建议使用撇号的位置来区分基数补码和减少的基数补码。在这种用法中,四的补码是指以四为底数的基数补码,而四位补码是指以五为底数的数的减基数补码。
按位取反
按位取反
是我们讨论补码的另一种计算方式,这也是上面反码
和补码
的取反操作。在编译器存储负数时,会采取按位取反
或按位取反加一
来实现对负数的二进制存储,以及在做减法时,对减数做此操作来获取作为加数的补码。
按位取反的真正含义应该是每一位
进行基数 - 1 - 数值
的操作,下面通过十进制和二进制的反码和补码分别说明。
十进制
先讨论十进制系统中对于一个整数 1523,求其反码和补码。我们把计算拆分到各个位上:
通过上面的拆解计算,我们可以得出,在 r 进制(基数)的系统中,已知一个整数,可以得出其反码
(减基数补码)的计算公式:
让 ,则 。
- 表示已知整数的每一位数值集合。例:整数 1523 的 集合为
上一篇: c++ 逐位逆转 - 金块
下一篇: 解释 php 中的位运算符
推荐阅读
-
韦根26协议读头的使用及proteus仿真-模拟韦根26读头的数据发送 使用定时器T1,采用16位定时器方式。 //8051 T1初始化 void Timer1_init { TMOD=0x10; //T1 16位定时器模式 ET1=0; //关闭定时器中断 TR1=0; //关闭定时器 TF1=0; //清除TF1标志 } 例如,就发送上面的这个数据:01000110111000001001010101 十进制的18580053 发送数据0的时候,就是将数据线D0拉低404us,发送数据1的时候,就是将数据线D1拉低404us。 首先设置定时器初值,用STC的下载器计算404us的预装入值。 拉低数据线,等待404us到时,之后抬高数据线,再等待2ms的时间,一位数据就发送完成了。 void Send_bit(bit bD) { //拉低数据线D0 404us TL1 = 0x8C; //设置定时初值 TH1 = 0xFE; //设置定时初值 if(bD==0) Send_D0=0; else Send_D1=0; TR1=1; //开启定时器 while(TF1 ==0); //等待溢出 //时间到抬高数据线 if(bD==0) Send_D0=1; else Send_D1=1; TF1=0; //清溢出标志 TR1=0; //关定时器 //下面是数据位的间隔 2ms TL1 = 0xCD; //设置定时初值 TH1 = 0xF8; //设置定时初值 TR1=1; //开启定时器 while(TF1 ==0); //等待溢出 TF1=0; //清溢出标志 TR1=0; //关定时器 } 将韦根26协议的数据装入一个无符号长整型变量里: //二进制 0 100011011100000100101010 1 头尾两位为奇偶校验位,十进制是18580053 unsigned long WG26=18580053; 无符号长整型是四个字节32位,装入26位的数据,则最前面的6位是无效的,循环移位6次,把无效数据移除。 //000000 01000110111000001001010101 for(i=0; i<6; i++) { WGdata=WGdata<<1; } //现在WGdata中的数据是 01000110111000001001010101 000000,后面多了6个0。 有效数据已经移动到最前面,可以开始发送了,循环26次发送数据 for(i=0; i<26; i++) { if( (WGdata & 0x80000000) == 0x80000000 ) Send_bit(1); //如果最高位为1,发送1 else Send_bit(0); //如果最高位为0,发送0 WGdata=WGdata<<1; //左移1位 } } 完整发送函数: //发送韦根26数据,用4个字节保存,一共32位 void SendWG26(unsigned long WGdata) { uchar data i; //从最高位开始发送数据,将开头的6个无效数据位隔过去 //18580053 //000000 01000110111000001001010101 //01000110111000001001010101 000000 for(i=0; i<6; i++) { WGdata=WGdata<<1; } //有效数据位已经移到了开头,开始发送数据 for(i=0; i<26; i++) { if( (WGdata & 0x80000000) == 0x80000000 ) Send_bit(1); else Send_bit(0); WGdata=WGdata<<1; } } 数据的接收 将数据线D0,D1连接到与门74HC08上,两条数据线上有数据发送时会产生INT0的下降沿中断。 (这只是仿真图,实际硬件连接有所不同) 在中断服务程序中接收数据: 还是用一个节的无符号长整型数据WG26,将收到的数据记入其最低位。每接到一位数据,左移一次。当接收到26个数据时,认为收到了读头发来的完整数据。设置接收完成标志ReceiveFlag=1;供主程序查询。 这里设置了一个超时检测,就是接收到的两位数据之间的时间间隔如果大于5ms就认为数据超时,(因为读头发来的数据每位之间的间隔是2ms)。这样,如果有意外的脉冲干扰,引起计数数据位的count值错误,也只会产生一次数据接收错误,将各种标志和变量全部清零后,不会影响下一次的数据接收。 在中断服务程序退出之前,一定要清除中断标志IE0,以免响应了无效数据的中断标志,产生接收错误。 void INT0_ISR(void) interrupt 0 //外部中断0服务程序 { //如果接到的两位数据之间间隔超过5ms,定时器溢出标志TF1置位 //超时检测使用定时器T1,16位定时方式 EX0=0; //关中断 //如果有定时器超时标志置位 if(TF1==1) //数据有误,放弃数据 { LCD_StrDisp(0x00,"Try Again "); LCD_StrDisp(0x40,"TimeOut Error "); Beep(10); //隔过至少一个数据包的时间,以便放弃不完整的数据 //延时100ms Delay50ms; Delay50ms; TR1=0; //关定时 TF1=0; //清标志 TL1 = 0x00; //设置定时初值 5ms 溢出 TH1 = 0xEE; //设置定时初值 5ms 溢出 count=0; WG26=0; ReceiveFlag=0; } //如果数据位间隔未超时 else { WG26=WG26<<1; if(RD0==0) //接收到了0 WG26=WG26&0xFFFFFFFE; else if(RD1==0) //接收到了1 WG26=WG26|0x00000001; count++; if(count==26) { count=0; ReceiveFlag=1; TR1=0; //关定时 TF1=0; //清标志 } else { //为接收下一位做准备 TR1 = 0; //关定时 TF1 = 0; //清除TF1标志 TL1 = 0x00; //设置定时初值 TH1 = 0xEE; //设置定时初值 //超过5ms溢出标志被置位 TR1 = 1; //定时器1开始计时 } } IE0=0; //清除INT0中断标志,很重要! EX0=1; //开中断 } 在主程序查询到接收完成标志后,开始对数据进行奇偶校验位的核对。 得到奇校验位,记入odd=1 将无效的6位移除 得到偶校验位,记入even=0 将偶校验位移除,统计前12位有几个1 100011011100 000100101010
-
二进制:有符号整数编码和加减运算
-
数的机器码表示:原码、反码、补码、变形补码、移码和浮点数编码-数学定义:例:+111的原码为0111,-101的原码为1101 (2) 纯小数的原码表示 纯小数的原码首位同样为符号位,后面的数值则表示小数的尾数,纯小数的整数位为默认为0无需表示。 例:+0.111的原码为0111,-0.101的原码为1101 可以看到,+111和+0.111的原码同为0111,这是因为约定的小数点位置不同,整数的原码的小数点约定在末尾,纯小数的原码的小数点约定在数值的最前面,这样通过约定小数点的位置来表示数的方法就称为定点数表示法,约定小数点位置实际上就是约定编码中每一位的权重。 二、反码 正数的反码与其原码相同。 负数的反码是其对应原码的符号位不变,数值位按位取反。 数学定义:例: 真值 +111 -101 +0.111 -0.101 原码 0111 1101 0111 1101 反码 0111 1010 0111 1010 三、补码 原码虽然转换很简单,但是在做减法时操作很复杂(减不够还要借位),因此计算机在做加负数操作时会先将负数的原码转换为补码再做加法。 先举个栗子,假设时钟现在是9点钟,我把时针往回拨3个小时是6点钟,或者顺时针往后拨9个小时还是6点钟,也就是说9-3的结果等同于9+9(mod 12),对于模数12,-3的补码为+9,这就引申出了一种将减法转换为加法的思想,把减去一个正数视为加上一个负数(例如9+(-3)),再将负数转换为对应的补码,最后就可以和补码做加法了,若结果超出了模数则丢弃一个模数即可。 如图所示:9减去灰色的部分(-3)就等同于加上蓝色的部分,即-3的补码即为蓝色部分的长度9(mod 12)。即补码=模数+真值(超出模数则舍弃一个模数) (1) 整数的补码表示 对于一个n位的二进制真值x,则取模数为2^(n+1),若x为正数则补码和原码相同(加上一个模数又需舍弃一个模数 故相同),若为负数则补码为模数加上x。相对于原码,补码这里的首位就不仅代表原数真值的符号了,也是补码自己的一个数值位。 取模数为2^(n+1)是因为在需要舍弃模数时只需要舍弃运算结果(二进制数)的最高位即可,这在计算机中很容易实现 数学定义:例:三位二进制数的模数2^4就是10000,故+111的补码为0111(即10000 + 111 = 0111 (舍弃模数位)),-101的补码为1011(即10000 - 101 = 1011) 补码运算示例:那么+111 - 101 = +111 + (-101) = 0111 + 1011 = 10010,运算结果只保留后四位(即舍弃模数位),故计算结果为0010。这样就通过加法实现了减法运算。 补码可表示数据范围:由数学定义可知,n位二进制补码可表示的数据范围为 -2n-1~2n-1-1。以8位的byte类型数为例,可表示的数据范围为 -27~27-1,即-128至+127,最小负数-128(补码:1000 0000),最大负数-1(补码:1111 1111),0(补码:0000 0000),最小正数1(补码:0000 0001),最大正数127(补码:0111 1111)。 由补码求真值:正数的补码即为原码即为真值,负数的真值由计算规则可知 负数真值= - (模数 - 补码),以补码1111 1111为例,其真值 = - (1 0000 0000 - 1111 1111) = - 0000 0001 = -1 (2) 纯小数的补码表示 对于一个纯小数x,则取模数为2^1,正数的补码和原码相同,负数的补码为模数2加上x。同样补码的首位不仅代表原数真值的符号,也是补码的数值位。 数学定义:例:纯小数的模数2就是10,故+0.111的补码为0111,-0.101的补码为1011(小数点约定在符号位后) 计算机中求补码的规则 可以注意到求负数的补码时还是要做减法,这在计算机中就很不方便了,但是通过其数学定义可以看到无论是整数还是纯小数,负数的补码都等于反码的末尾加1,而这又等同于原码数值位从右向左遇到第一个1后,这个1左边的数值位都按位取反,故实际计算机中求补码的规则如下:正数的补码等于原码负数的补码等于原码的数值位从右向左的第一个1左边的所有数值位按位取反(例:byte类型值-6的原码为1000 0110,则其补码为1111 1010) 四、变形补码 两个补码在运算时可能会溢出从而产生错误的结果,比如0111+0101 = 1100,两个正数相加反而得到了一个负数,那么在计算机中要如何判断运算结果是否溢出了呢,这就引申出了变形补码。从直观上看,相对于补码来说变形补码就是用两位来表示符号位,00表示正数,11表示负数。运算结果符号位为01表示正溢出,10表示负溢出。
-
Python 编码及运算符详细讲解-在计算机硬件中,编码(coding)是指用代码来表示各组数据资料,使其成为可利用计算机进行处理和分析的信息。代码是用来表示事物的记号,它可以用数字、字母、特殊的符号或它们之间的组合来表示。 2.编码的种类(常用种类) ①ASCCI 1.ASCCI的产生 在计算机中,所有的数据在存储和运算时都要使用二进制数表示(因为计算机用高电平和低电平分别表示1和0),例如,像a、b、c、d这样的52个字母(包括大写)、以及1等数字还有一些常用的符号(例如*、#、@等)在计算机中存储时也要使用二进制数来表示,而具体用哪些二进制数字表示哪个符号,当然每个人都可以约定自己的一套(这就叫编码),而大家如果要想互相通信而不造成混乱,那么大家就必须使用相同的编码规则,于是美国有关的标准化组织就出台了ASCII编码,统一规定了上述常用符号用哪些二进制数来表示。 2.ASCCI的表述 ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。标准ASCII 码也叫基础ASCII码,使用7 位二进制数(剩下的1位二进制为0)来表示所有的大写和小写字母,数字0 到标点符号, 以及在美式英语中使用的特殊控制字符。 字母A用ASCII编码是十进制的65,二进制的01000001; ②unicode 1.Unicode的产生