(CSAPP笔记) – 二进制

1.大端:高的有效位保存在低地址中;小端:高的有效位保存在高地址中。

可以通过代码验证一下:

// 函数解释器.cpp : 定义控制台应用程序的入口点。
//

#include "stdio.h"

typedef unsigned char *byte_ptr; 
void showbits(byte_ptr b,int len)
{
	for(int i=0;i<len;++i)
	{
		printf("Address is 0x%x, Value is 0x%.2x\n",b,b[i]);
	}
	printf("\n");
}
int main()
{
	int ii = 3510593;
	int iihexa=0x00359141;
	float f=3510593.0;
	float fhexa=0x4A564504;
	
	showbits((byte_ptr)&ii,sizeof(ii));
	showbits((byte_ptr)&iihexa,sizeof(iihexa));
	showbits((byte_ptr)&f,sizeof(f));
	showbits((byte_ptr)&fhexa,sizeof(fhexa));
	
    return 0;
}

例如:iihexa的四个字节被填入0x00359141,换句话说指定了iihexa的补码为0x00359141。0x41、0x91……0x00按照内存地址从低到高的位置保存。

2.在Windows环境下,G++和VC的编译器给出的long的大小在32位和64位的情况下是一致的。Linux还需要验证。

3.无符号数的编码:位相量x  B2Uw(Binary to unsigned) = Σ(0,w-1,xi * 2^i)  sum(i,j,exp)表示的是从i=i的范围到j,对于表达式exp的值的和(就是Σ) w是长度。

4.补码的编码:负数可以用补码(Two's complement)表示。最高位作为负数的负权。B2Tw= -x(w-1) * 2^(w-1) +  Σ(0,w-2,xi * 2^i)。所以相当于取绝对值运算,以后直接可以把负数转换为补码,就不需要通过将其绝对值取反 +1编程补码了。例如 (-1)=(1111)2=-2^3 + 1*2^2 + 1*2^1 + 1*2^0。

5.对于取值范围的理解:有符号数的最小范围:就是负权的值最大,其余位为0,所以就是100……0 到0111……1。

  • 无符号转有符号:由于有符号的数只有2^(w-1)个数据位,所以所有大于或等于2^(w-1)的数就会被解释为负数(因为负权的位置被解释为1),因为前面w-1位的和不可能与-2^w抵消。所以当u>=2^(w-1)时,u的无符号位u-2^w。U2Tw(u)=u 或 u-2^w(当u>=2^(w-1)。
  • 有符号转无符号:由于无符号最高位为数据位,所以转换后数字会特别大。转换后的数据为x(w-1)*2^w + x就可以表示。T2Uw(x)=x(w-1)*2^w + x

6.位扩充:对于有符号数,会发生符号位扩充,最高位将会扩充。对于无符号数,最高位会补零。

7.移位运算:同上的情况,有符号会算数移位(布最高符号位);无符号补0。他们都会舍弃多余的二进制位。

8.数字截断:注意被截取数字都视为有符号的将长位w的二进制截取位k位的二进制

  • 根据推理表明:B2Tw([xw-1,xw-2……x0]) mod 2^k=B2Uk[xk-1,xk-2,……,x0]。有公式 x mod y = x mod y = x - y  * floor(x / y)。floor是取下界符号。w位截到k位,就是向右移(w-k)位,相当于乘以 1/(2^(w-k)) 也就相当于无符号数 x mode 2^k。
  • 无符号数字截断(二进制):B2Uk([xk-1,xk-2,xk-3……x0]) = B2Uw([xw-1,xw-2……x0]) mod 2^k 不过由于截断操作一般是得到有符号的所以需要把有符号的转为无符号的,所以需要取一次余。其实将有符号的数字转为无符号可以利用公式s % 2^k = u。表示的就是将有符号的s转为k位的无符号的数。之所以这么转换是因为截取的补码可能最高为1,表示负数。
  • 补码数字截断(可能是负数):B2Tk([xk-1,xk-2,xk-3……x0]) = U2Tw(B2Uw([xw-1,xw-2……x0]) mod 2^k )。

9.类型转换:首先更改大小,然后是变换符号例如:short转unsigned,顺序是short->signed int->unsigned int。

10. B2Uw:长为w的无符号的二进制向量。 B2Tw:长为w的有符号的补码的二进制向量。 U2Tw:表示将长位w的无符号数转有符号数的函数。  T2Uw:表示将长位w的有符号数转无符号数的函数。

11.整数运算:

11.1 无符号加法:注意有可能会有溢出的情况如。如果x + y < 2^w。则和的最高位会为0,如果2^w <=x+y<2^(w+1) 那么就会发生溢出,所以x+y=x+y-2^w 来表示。

11.2 算数运算溢出:w位的的无符号的数的集合,执行加法运算+(u,w)。对于每个值x,必然 有某个值-(u,w)x 满足-(u,w)x + (u,w)x = 0。-(u,w)x是(对于无符号)加法逆元。加法逆元-(u,w)x表达为:当x=时,为0;当x>0时,2^w - x表示。

11.3 补码的加法:设x+y=z。

四种情况:见书上P57页。对于-2^(w-1)<= x,y <=2^(w-1)-1之内的数。

他们的和 x+(t,w)y=

11.3.1: x+y-2^w   当2^(w-1)<=x+y   正溢出

11.3.2: x+y          当-2^(w-1)<= x+y <=2^(w-1)-1  正常

11.3.3: x+y+2^w  当x+y < -2^(w-1)  负溢出

11.4 计算机判断溢出:https://www.zhihu.com/question/22199029

12. 补码的非:对于有符号-(t,w)

-(t,w)x=-2^(w-1) ,当x=-2^(w-1);-x,当x>-2^(w-1)。原因是-2^(w-1)的逆元2^(w-1)在有符号下无法表示。

13.乘法:

  • 无符号的乘法:对于满足0<=x,y<=UMaxw的x,y有:x * (u,w)y = (x*y) mod 2^w。
  • 补码乘法:对于满足TMinw<=x,y<=UMaxw的x,y有:x * (t,w)y = U2Tw((x*y) mod 2^w)。也等于U2Tw((x*y) - 2^w)
  • 无符号与有符号的二进制乘法虽然位级不同,但是截取到w位的位级是相同的。

15.乘以常数:

乘以常数可以改写为加法例如:1*14 == 1*(2^3+2^2+2^1) == 2^3 + 2^2 + 2^1 = 1<<3 + 1<<2 +1<<1.减法也是一样。但是,这样可能会导致溢出。即使溢出的时候,我们通过移位得到的结果也是一样的。可以通过截断(溢出值 mod 2^w)。

16.除以2的幂:需要算术移位:

一般而言,向右移位可能会产生小数(我们谈的是整数),所以肯定会有一个取整的过程,那么究竟是怎样的方式呢?补码除以2的幂,将会向下舍入:推导P73。例如x=-12340 除以16 = -771.25 向下舍入的话就会的得到-772,在某种意义上说,这是不对的。所以需要通过偏置来修正。对于整数x和y(y>0),ceil(x/y)=floor((x+y-1) / y)。ceil(x/y)=floor((x+y-1)/y),假设x=qr+y,q是商,y可以看作余数。得到(x+y-1)/y=q+(r+y-1),因此floor(x+y-1)=q+floor((r+y-1) / y)。当r=0时,后一项为0;当r>0时,后一项为1。(y-2<=r+y<=y-2,当r>0且r<y时,1<(y+y-1)/y<2)。通过给x增加偏量y-1,然后将除法向下舍入,当y整除x时,我们得到q,否则就是q+1。

对于除以2的幂,y=2^k。所以若x=(x <0?x+(1<<k)-1:x)>>k 就可以避免除法的向下取整问题。

或者也可以这样((x>>31) & 0x0f)+x 表示的就是将int类型的除以2^4。需要加上偏量1<<4-1=15

17.快速求负数(正数x的逆元): 正数的源码的反码+1 也就是 -x=~x+1。转至:补码(为什么按位取反再加一):告诉你一个其实很简单的问题

要求-x可以利用0-x来求出,而0等于11111111+00000001 所以-x=(11111111+00000001)-x=11111111-x+00000001=取反操作+1