基础荒野:有符号整数详解
Breif
本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004的原因,但发现自己对计算机的数字表示和运算十分陌生,于是只好恶补一下。
本篇我们一起来探讨一下基础——有符号整数的表示方式和加减乘除运算。
Encode
有符号整数可表示正整数、0和负整数值。其二进制编码方式包含 符号位 和 真值域。
我们以8bit的存储空间为例,最左1bit为符号位,而其余7bit为真值域,因此可表示的数值范围是{-128,...,127},对应的二进制补码编码是{10000000,...,01111111}。
从集合论的角度描述,我们可以将十进制表示的数值范围定义为集合A,将二进制表示的数值范围定义为集合B,他们之间的映射为f。f(a)=b,其中a属于A、b属于B。并且f为双射函数。因此有符号整数表示方式具有如下特点:
1. 可表示的数值范围小;
2. 十进制表示的数值范围与二进制表示的数值范围的元素是一一对应的,两者可精确映射转换。(相对浮点数而言,某些二进制表示的数值只能映射为十进制表示的数值的近似值而已);
3. C语言中虽然没有规定必须采用补码来对有符号数进行编码,但大部分实现均是采用补码。而Java和C#则明确规定采用补码来表示有符号数。
Sign-extended
符号扩展运算用于在保持数值不变、符号位不变的前提下,不同字长的整数之间的转换。
例如现在我们要将8bit的10000100扩展为16bit,那么我们只要将高8bit设置为与原来符号位相同的值(这里是1)即得到1111111110000100,而其数值和符号并不产生变化。
Truncation
截断会减少位数,并对原始值取模。模为2^n,n为截断后的位数。
例如现在将16bit的100000100000000100截断为8bit,那么结果为00000100,而模是2^8。
Addition
注意:位级运算均是模数运算,即加减乘除后均会对运算结果取模,并以取模后的结果作为终止返回。
有符号整数加法的运算顺序:
1. 算术加法(由于采用补码对有符号数进行编码,则是已经将负数转换为正数存储,所以含负数的加法只需要直接执行算术加法即可);
2. 执行截断操作。
示例1,两个4bit的有符号数相加(3+6):
0011
+0110
1001,然后执行截断得到1001,发生正溢出得到 -7
示例2, 两个4bit的有符号数相加(-3+6):
1101
+0110
10011,然后执行截断得到0011,发生正溢出得到 3
Subtraction
有符号整数减法的运算顺序:
1. 将减法转换为加法(对减数取补码);
2. 算术加法;
3. 执行截断操作。
示例1,两个4bit的有符号数相减(-5-6):
1011
-0110
对减数求补码后,减法转换为加法
1011
+1010
10101,然后执行截断得到0101,发生负溢出得到5
示例2,两个4bit的有符号数相减(-5-(-6)):
1011
-1010
对减数求补码后,减法转换为加法
1011
+0110
10001,然后执行截断得到0001,得到1
Multiplication
对于乘法实质上就是通过移位操作和加、减法组合而成。
1. 将乘数以二进制形式表示,并以连续的1作为分组。如-5的二进制形式为(1)0(11),从左至右可分成2组分别是(1)、(11)。
2. 以n表示每组的最高位的指数,以m表示每组最低位的指数。如第一组n=m=3,第二组n=1而m=0。
3. 根据公式(x<<n+1)-(x<<m)对每组进行运算,并将结果相加。如(假设被乘数为-1)
第一组:(1111)<<(3+1) - (1111)<<3 = 0000 - 1000 = 0000 + 1000 = 1000
第二组:(1111)<<(1+1) - (1111)<<0 = 1100 - 1111 = 1100 + 0001 = 1101
两组相加:1000 + 1101 = 10101,截断得到0101,等于十进制数值5.
2.4. 对结果取模。
Division
对于除法实质上就是通过移位操作和加、减法组合而成,且根据除数是否为2的n次幂(n为正数)区别处理。
1. 对于被除数为2的n次幂(n为正数)的情况,除法公式为:a>>n,如-6/4等价于6/(2^2),则可转换为移位操作-6>>2即可。然后再对结果取模。
2. 对于被除数不为2的n次幂(n为正数)的情况,则情况复杂不少。运算步骤如下:(实质上我们就是按这个步骤做十进制除法的)
2.1. 对负数取补,提取符号乘积。
2.2. 高位对齐,在除数值小于被除数值的前提下,让除数的位数等于被除数;若执行高位对齐后,除数值大于被除数时,则除数右移一位。得到位移数。
2.3. 试商,除数-被除数*N = 余数中间值 ,其中N*被除数 <= 除数 && (N+1)*被除数 > 除数。商 = 商 + N * 基数^位移数。
2.4. 循环执行上述步骤,直到无需再执行高位对齐,那么2.2中得到的余数中间值将作为除法运算的最终余数,否则余数中间值则作为一下轮高位对齐的被除数处理。
2.5. 符号乘积乘以商得到最终商,符号乘积乘以余数得到最终余数。
C语言实现:
#include <stdio.h>
// 前置条件
const char lowest_bit_weight = 1; // 二进制最低位的位权重
int main(){
// 输入
char dividend = -5, divisor = -2;
// 输出
char quotients = 0, // 商
rem = 0; // 余数
// 中间值
char highest_bit_weight,
divisor_aligned,
tmp_dividend = dividend,
tmp_divisor = divisor;
char high_alignment;
char sign,
sign1 = 1,
sign2 = 1;
// 负数转换为正数, 求符号乘积
if (tmp_dividend < 0){
tmp_dividend = ~tmp_dividend;
tmp_dividend += 1;
sign1 = ~sign1;
sign1 += 1;
}
if (tmp_divisor < 0){
tmp_divisor = ~tmp_divisor;
tmp_divisor += 1;
sign2 = ~sign2;
sign2 += 1;
}
sign = sign1 * sign2;
// 开始运算
while (1){
// 高位对齐 (从高位开始运算)
// 结果:1. 要么被除数的最高位小于除数的最高位;
// 2. 要么被除数的最高位对齐除数的最高位, 且被除数大于除数;
high_alignment = 0;
highest_bit_weight = lowest_bit_weight;
divisor_aligned = tmp_divisor;
while (tmp_dividend >= divisor_aligned){
divisor_aligned = divisor_aligned << 1;
highest_bit_weight = highest_bit_weight << 1;
high_alignment += 1;
}
if (high_alignment > 0){
divisor_aligned = divisor_aligned >> 1;
highest_bit_weight = highest_bit_weight >> 1;
high_alignment -= 1;
}
// 当无需执行高位对齐时,则将下一轮的被除数作为余数,并且结束运算
if (0 == high_alignment) {
rem = tmp_dividend;
break;
}
// 上一轮运算的商加上最高位权重得到当前运算的商值
quotients = quotients | highest_bit_weight;
// 被除数减除数的差值作下一轮的被除数
tmp_dividend = tmp_dividend - divisor_aligned;
}
// 商*符号乘积 = 最终商,余数*符号乘积 = 最终余数
printf("%d/%d=%d(rem:%d)\n", dividend, divisor, quotients * sign, rem * sign);
return 0;
}
Convert Unsigned 2 Signed, and Convert Signed 2 Unsigned
无符号数与有符号数间转换采取的是位级表示(位模式)不变,解析方式变化引起最终所表示的值变化。
例如:无符号数15的4bit位模式为1111,强制转换为有符号数时其位模式依然是1111,但实际表示的值则变为-1。
无符号数转换为有符号数的公式 U2Tw(x) = x - xw-1*2w,其中w表示位数,x表示无符号数的十进制值,x表示无符号数的二进制位模式。
有符号数转换为无符号数的公式 T2Uw(x) = x + xw-1*2w,其中w表示位数,x表示无符号数的十进制值,x表示无符号数的二进制位模式。
注意:在C语言中若参与运算的两运算数分别是有符号数和无符号数,那么会隐式将有符号数转换为无符号数后再进行运算。
Conclusion
尊重原创,转载请注明
Thanks
《深入理解计算机系统》
上一篇: 6-基本数据类型
推荐阅读
-
基础荒野:有符号整数详解
-
韦根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
-
二进制:有符号整数编码和加减运算
-
C 语言系列 (II) 有符号数和无符号数详解
-
[编程基础] 用 c 语言获取整数和浮点数的符号位
-
PHP中把有符号整数转换成无符号整数的方法,php integer_PHP教程
-
5.1.4 有符号整数的表示与运算_正反补
-
F#探险之旅(二):函数式编程(上)-函数式编程范式简介 F#主要支持三种编程范式:函数式编程(Functional Programming,FP)、命令式编程(Imperative Programming)和面向对象(Object-Oriented,OO)的编程。回顾它们的历史,FP是最早的一种范式,第一种FP语言是IPL,产生于1955年,大约在Fortran一年之前。第二种FP语言是Lisp,产生于1958,早于Cobol一年。Fortan和Cobol都是命令式编程语言,它们在科学和商业领域的迅速成功使得命令式编程在30多年的时间里独领风骚。而产生于1970年代的面向对象编程则不断成熟,至今已是最流行的编程范式。有道是“*代有语言出,各领风骚数十年”。 尽管强大的FP语言(SML,Ocaml,Haskell及Clean等)和类FP语言(APL和Lisp是现实世界中最成功的两个)在1950年代就不断发展,FP仍停留在学院派的“象牙塔”里;而命令式编程和面向对象编程则分别凭着在商业领域和企业级应用的需要占据领先。今天,FP的潜力终被认识——它是用来解决更复杂的问题的(当然更简单的问题也不在话下)。 纯粹的FP将程序看作是接受参数并返回值的函数的集合,它不允许有副作用(side effect,即改变了状态),使用递归而不是循环进行迭代。FP中的函数很像数学中的函数,它们都不改变程序的状态。举个简单的例子,一旦将一个值赋给一个标识符,它就不会改变了,函数不改变参数的值,返回值是全新的值。 FP的数学基础使得它很是优雅,FP的程序看起来往往简洁、漂亮。但它无状态和递归的天性使得它在处理很多通用的编程任务时没有其它的编程范式来得方便。但对F#来说这不是问题,它的优势之一就是融合了多种编程范式,允许开发人员按照需要采用最好的范式。 关于FP的更多内容建议阅读一下这篇文章:Why Functional Programming Matters(中文版)。F#中的函数式编程 从现在开始,我将对F#中FP相关的主要语言结构逐一进行介绍。标识符(Identifier) 在F#中,我们通过标识符给值(value)取名字,这样就可以在后面的程序中引用它。通过关键字let定义标识符,如: let x = 42 这看起来像命令式编程语言中的赋值语句,两者有着关键的不同。在纯粹的FP中,一旦值赋给了标识符就不能改变了,这也是把它称为标识符而非变量(variable)的原因。另外,在某些条件下,我们可以重定义标识符;在F#的命令式编程范式下,在某些条件下标识符的值是可以修改的。 标识符也可用于引用函数,在F#中函数本质上也是值。也就是说,F#中没有真正的函数名和参数名的概念,它们都是标识符。定义函数的方式与定义值是类似的,只是会有额外的标识符表示参数: let add x y = x + y 这里共有三个标识符,add表示函数名,x和y表示它的参数。关键字和保留字关键字是指语言中一些标记,它们被编译器保留作特殊之用。在F#中,不能用作标识符或类型的名称(后面会讨论“定义类型”)。它们是: abstract and as asr assert begin class default delegate do donedowncast downto elif else end exception extern false finally forfun function if in inherit inline interface internal land lazy letlor lsr lxor match member mod module mutable namespace new nullof open or override private public rec return sig static structthen to true try type upcast use val void when while with yield 保留字是指当前还不是关键字,但被F#保留做将来之用。可以用它们来定义标识符或类型名称,但编译器会报告一个警告。如果你在意程序与未来版本编译器的兼容性,最好不要使用。它们是: atomic break checked component const constraint constructor continue eager event external fixed functor global include method mixinobject parallel process protected pure sealed trait virtual volatile 文字值(Literals) 文字值表示常数值,在构建计算代码块时很有用,F#提供了丰富的文字值集。与C#类似,这些文字值包括了常见的字符串、字符、布尔值、整型数、浮点数等,在此不再赘述,详细信息请查看F#手册。 与C#一样,F#中的字符串常量表示也有两种方式。一是常规字符串(regular string),其中可包含转义字符;二是逐字字符串(verbatim string),其中的(")被看作是常规的字符,而两个双引号作为双引号的转义表示。下面这个简单的例子演示了常见的文字常量表示: let message = "Hello World"r"n!" // 常规字符串let dir = @"C:"FS"FP" // 逐字字符串let bytes = "bytes"B // byte 数组let xA = 0xFFy // sbyte, 16进制表示let xB = 0o777un // unsigned native-sized integer,8进制表示let print x = printfn "%A" xlet main = print message; print dir; print bytes; print xA; print xB; main Printf函数通过F#的反射机制和.NET的ToString方法来解析“%A”模式,适用于任何类型的值,也可以通过F#中的print_any和print_to_string函数来完成类似的功能。值和函数(Values and Functions) 在F#中函数也是值,F#处理它们的语法也是类似的。 let n = 10let add a b = a + blet addFour = add 4let result = addFour n printfn "result = %i" result 可以看到定义值n和函数add的语法很类似,只不过add还有两个参数。对于add来说a + b的值自动作为其返回值,也就是说在F#中我们不需要显式地为函数定义返回值。对于函数addFour来说,它定义在add的基础上,它只向add传递了一个参数,这样对于不同的参数addFour将返回不同的值。考虑数学中的函数概念,F(x, y) = x + y,G(y) = F(4, y),实际上G(y) = 4 + y,G也是一个函数,它接收一个参数,这个地方是不是很类似?这种只向函数传递部分参数的特性称为函数的柯里化(curried function)。 当然对某些函数来说,传递部分参数是无意义的,此时需要强制提供所有参数,可是将参数括起来,将它们转换为元组(tuple)。下面的例子将不能编译通过: let sub(a, b) = a - blet subFour = sub 4 必须为sub提供两个参数,如sub(4, 5),这样就很像C#中的方法调用了。 对于这两种方式来说,前者具有更高的灵活性,一般可优先考虑。 如果函数的计算过程中需要定义一些中间值,我们应当将这些行进行缩进: let halfWay a b = let dif = b - a let mid = dif / 2 mid + a 需要注意的是,缩进时要用空格而不是Tab,如果你不想每次都按几次空格键,可以在VS中设置,将Tab字符自动转换为空格;虽然缩进的字符数没有限制,但一般建议用4个空格。而且此时一定要用在文件开头添加#light指令。作用域(Scope)作用域是编程语言中的一个重要的概念,它表示在何处可以访问(使用)一个标识符或类型。所有标识符,不管是函数还是值,其作用域都从其声明处开始,结束自其所处的代码块。对于一个处于最顶层的标识符而言,一旦为其赋值,它的值就不能修改或重定义了。标识符在定义之后才能使用,这意味着在定义过程中不能使用自身的值。 let defineMessage = let message = "Help me" print_endline message // error 对于在函数内部定义的标识符,一般而言,它们的作用域会到函数的结束处。 但可使用let关键字重定义它们,有时这会很有用,对于某些函数来说,计算过程涉及多个中间值,因为值是不可修改的,所以我们就需要定义多个标识符,这就要求我们去维护这些标识符的名称,其实是没必要的,这时可以使用重定义标识符。但这并不同于可以修改标识符的值。你甚至可以修改标识符的类型,但F#仍能确保类型安全。所谓类型安全,其基本意义是F#会避免对值的错误操作,比如我们不能像对待字符串那样对待整数。这个跟C#也是类似的。 let changeType = let x = 1 let x = "change me" let x = x + 1 print_string x 在本例的函数中,第一行和第二行都没问题,第三行就有问题了,在重定义x的时候,赋给它的值是x + 1,而x是字符串,与1相加在F#中是非法的。 另外,如果在嵌套函数中重定义标识符就更有趣了。 let printMessages = let message = "fun value" printfn "%s" message; let innerFun = let message = "inner fun value" printfn "%s" message innerFun printfn "%s" message printMessages 打印结果: fun value inner fun valuefun value 最后一次不是inner fun value,因为在innerFun仅仅将值重新绑定而不是赋值,其有效范围仅仅在innerFun内部。递归(Recursion)递归是编程中的一个极为重要的概念,它表示函数通过自身进行定义,亦即在定义处调用自身。在FP中常用于表达命令式编程的循环。很多人认为使用递归表示的算法要比循环更易理解。 使用rec关键字进行递归函数的定义。看下面的计算阶乘的函数: let rec factorial x = match x with | x when x < 0 -> failwith "value must be greater than or equal to 0" | 0 -> 1 | x -> x * factorial(x - 1) 这里使用了模式匹配(F#的一个很棒的特性),其C#版本为: public static long Factorial(int n) { if (n < 0) { throw new ArgumentOutOfRangeException("value must be greater than or equal to 0"); } if (n == 0) { return 1; } return n * Factorial (n - 1); } 递归在解决阶乘、Fibonacci数列这样的问题时尤为适合。但使用的时候要当心,可能会写出不能终止的递归。匿名函数(Anonymous Function) 定义函数的时候F#提供了第二种方式:使用关键字fun。有时我们没必要给函数起名,这种函数就是所谓的匿名函数,有时称为lambda函数,这也是C#3.0的一个新特性。比如有的函数仅仅作为一个参数传给另一个函数,通常就不需要起名。在后面的“列表”一节中你会看到这样的例子。除了fun,我们还可以使用function关键字定义匿名函数,它们的区别在于后者可以使用模式匹配(本文后面将做介绍)特性。看下面的例子: let x = (fun x y -> x + y) 1 2let x1 = (function x -> function y -> x + y) 1 2let x2 = (function (x, y) -> x + y) (1, 2) 我们可优先考虑fun,因为它更为紧凑,在F#类库中你能看到很多这样的例子。 注意:本文中的代码均在F# 1.9.4.17版本下编写,在F# CTP 1.9.6.0版本下可能不能通过编译。 F#系列随笔索引页面