读书笔记：整数位表示

From : Computer System ( A Programmer's Perspective)

 

整数分为正整数，0，负整数, 当今负整数使用补码表示，方便机器运算。

 

正整数

 

二进制表示为

 

0Xw-1Xw-2..X0  =Xw-1* 2^(w-1) + Xw-2 * 2^(w-2)....+X0*1

 

正整数进行扩展时，增加的位用0填充

 

负整数

 

二进制表示为

 

1Xw-1Xw-2..X0  =-1*2^(w) + Xw-1* 2^(w-1) + Xw-2 * 2^(w-2)....+X0*1

 

假设负整数为 F，相同的二进制表示的正数为 P，则 P-F = 2^(w+1)

 

扩展

 

负整数进行扩展时,增加的位用1填充

 

11Xw-1Xw-2..X0  =-1*2^(w+1) +  2^(w) + Xw-1 * 2^(w-1)....+X0*1

                          =-1*2^(w) + Xw-1* 2^(w-1) + Xw-2 * 2^(w-2)....+X0*1

                          = 1Xw-1Xw-2..X0

 

从正整数得到负整数

 

从一个正整数快速得到其负整数的二进制表示的快捷方法有：

 

 

1.正整数二进制去反加一

 

2.假设正整数二进制为 Xw...Xw-x1000..0 ,则Xw 到 Xw-x 所在位取反，其它位保持不变即可。

 

负整数除法问题

 

-7/2 = -4 而不是常见舍入零的表示 -3 ，扩展到任意 -y/x (x,y>0)，要想得到舍入零的表示需要预先进行偏置

 

(-y+x-1) / x

 

 

0

 

永远用 00000..0 表示

 

乘法操作

 

可转为更加快速的移位操作

 

n*K

 

K=00000Xw....Xz000

 

其中  Xw 到 Xz 为 1

 

则 n*K = n<<w + n<<(w-1)+...+n<<z = n<<(w+1)-n<<z

 

 

溢出问题

 

补码运算注意溢出问题，包括负溢出（两个负整数相加得到一个正数），正溢出（两个正整数相加得到负数)