Posted on | In | Visitors:

感觉看csapp真的能学到不少东西，因此特别写一篇博客来记录csapp中学习内容

1.信息的表示和处理

1.2进制与16进制

信息在计算机中以2进制的形式表达，不过16进制更直观，很多例子都是通过16进制展示(二进制太长了)
关于2进制与16进制，每4位二进制可以表达一位16进制，如1111 == 0xf

2.不同整数类型所占字节数

1byte表示1个字节，word == 2byte，dword = 4byte，qword = 8byte
unsigned表示无符号，当使用unsigned后，符号位变成数值位，对应的范围* 2 + 1
char 占 1byte，范围位 -128，127
short 2byte
int 4
long 4 (64位中为8)
int32_t 4
int64_t 8

大端与小端表示法
例子0x123456
在小端中56 34 12
大端中 12 34 56

3.补码、反码和原码

如图

4.浮点数

32位浮点数的计算方法float=(-1)^s * M * 2^E float的表示方法，1个二进制位表示符号s，
8个二进制位表示阶码(e为无符号数)，23个二进制位表示小数部分(f) (规格化数，即e!=0,且e!=255)
E = e - Bias Bias =2^(k-1) - 1, 举个栗子，e 为 1111 1110 ,
此时 Bias = 127, e = 254 - 127 = 127 假设 M 为 1 00 0000 0000 0000 0000 0000 M = 1 + f ，
f部分为f = 1 * 2^-1 …… + 0 = 0.5 用小数点表示 M
即 1.100000……000 (非规格化数)E = 1 - Bias, M = f = 1

2.程序的机器级表示

1.Intel和ATT格式区别

1.Intel省略大小后缀q，如push和mov，而不是pushq和movq
2.Intel省略寄存器前的%,如eax，而不是%eax
3.Intel使用不同的方式描述内存中的位置，如’QWORD PTR [rbx]’而不是’%rbx’
4.当带有多个操作数时，列出操作数的顺序相反，如mov eax，ebx(eax=ebx)

2.内联汇编

当使用c无法实现、而使用汇编能实现时，可以在将程序与汇编结合
1.编写完整的函数，放进一个独立的汇编代码文件中，让汇编器和链接器把它和用c语言书写的代码合并
2.使用GCC的内联汇编特性，用asm伪指令可以在c中包含简短的汇编代码

3.各寄存器的作用

4.寻址方式


5.数据传送指令

movb 传byte
movw 传word
movl 传dw
movq 传qw
mvoabsq I，R R<-I 传送绝对的四字(常规的movq只能表示为32为补码数字的立即数作为源操作数，然后把这个值符号扩展得到64位的值)
关于零扩展的数据传送指令

6.整数算数操作

关于lea还有dec、inc、neg等操作(csapp yyds，早知道当初就认认真真的学一遍csapp)

7.条件码寄存器

用以描述最近的算术或逻辑操作的属性。
CF:进位标志。可以用来检查无符号的溢出
ZF:零标志。最近的操作得出的结果为0
SF:符号标志。最近的操作得到的结果为负数
OF:溢出标志。最近的操作导致一个补码溢出———正溢出或者负溢出
除了lea，6中的所有指令都会设置条件码

8.set指令

如图

9.跳转指令

看到这里感觉自己知识还是太浅薄了

10.条件传送指令

11.媒体寄存器

12.浮点传送指令

13.浮点数运算指令

Posted on | In | Visitors:

csapp的实验确实有点东西，感觉学到了不少东西
数据实验

前置知识：

~ ：非运算符 如 ~0010 = 1101
& ：与运算符 如 0010 & 1110 = 0010
| ：或运算符 如 0010 | 1110 = 1110
^ ：异或运算符 如 1001 ^ 0110 = 1111
! ：逻辑非运算符 如 !0 = 1 !1 = 0
&&:逻辑与运算符 如 1 && 1 = 1 1 && 0 =0
||：逻辑或运算符 如 1 || 0 = 1 
>>: 右移运算符 逻辑右移(不考虑符号位) 如0100 >> 2 = 0001
              算术右移(考虑符号位，是什么补什么) 如 1001 >> 2 = 1110
<<: 左移运算符 如 1001 1001 << = 0110 0100

浮点数

计算方法float=(-1)^s * M * 2^E
float的表示方法，1个二进制位表示符号s，8个二进制位表示阶码(e为无符号数)，23个二进制位表示小数部分(f)
(规格化数，即e!=0,且e!=255)E = e - Bias Bias =2^(k-1) - 1,
举个栗子，e 为 1111 1110 ,此时 Bias = 127, e = 254 - 127 = 127
假设 M 为 1 00 0000 0000 0000 0000 0000
M = 1 + f ，f部分为f = 1 * 2^-1 …… + 0 = 0.5
用小数点表示 M 即 1.100000……000
(非规格化数)E = 1 - Bias, M = f = 1

1.xor

题目要求只是用 ~ 和 & 来实现 异或 即 ^, 本质就是相同位取1、不同位取0，而每一位又只有0或1，
感觉我是试出来的
如下
即

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int bitXor(int x, int y) {
  return ~(~(~x&y)&~(~y&x));

// 1111 0011 1111 x
// 1001 1000 0001 y

// 0000 1100 0000 ~x
// 0110 0111 1110 ~y

// 0000 1000 0000 ~x&y
// 0110 0011 1110 ~y&x

// 1111 0111 1111 ~(~x&y)
// 1001 1100 0001 ~(~y&x)

// 1001 0100 0001
// 0110 1011 1110 reuslt
//~(~(~x&y)&~(~y&x))
}

2.返回最小二进制整数

最小二进制整数即符号位为1，其它位都为0，int占4个byte，一个byte占8个二进制位

1
2
3
int tmin(void) {
  return 1<<31;
}

3.判断x是否位最大二进制整数

最大二进制整数即上一个结果取反，题目要求是返回1，否返回0
思路：0x7fffffff + 1 = ~ 0x7fffffff,有个特例是x为-1的时候，!(!(x^-1))这个为特判

1
2
3
int isTmax(int x) {
  return !((x+1)^(~x))&!(!(x^-1));
}

4.所有奇数位为1返回1，否则返回0

案例为：allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
思路:先得到0xaaaa，然后再异或两次就可以了，一开始没注意<< 和 + 的优先级，一直错了

1
2
3
4
int allOddBits(int x) {
  int temp=0xaa+(0xaa<<8);//0xaaaa
  return !((x&temp)^temp)&!(((x>>16)&temp)^temp);
}

5.返回相反数

1的二进制形式是0000 0001 -1的二进制形式1111 1111,从 x + -x -1 == 1111 1111(2) 可以直接看出来 -x = ~ x + 1 

1
2
3
int negate(int x) {
  return ~x+1;
}

6.若 0x30<=x<=0x39返回1，否则返回0

9=(1001)(2)
3=(0011)(2)
思路:先判断0x30和0x39中相同的3，即0011，此然后再判断后一位，后一位有两种情况：
1.1xxx –> !(x>>1&1|x>>2&1)
2.0xxx –> !(x>>3&1)

1
2
3
int isAsciiDigit(int x) {
  return !(x>>4^3)&(!(x>>3&1)|!(x>>1&1|x>>2&1));
}

7.使用运算符表示？：

例子：conditional(2,4,5) = 4
思路:突然想到一个特别关键的点，然后就做出来了，1往左移31位，得到最小整数，再往右移，此时因为
符号位为1，再往右移31位得到的就是-1,而先往左移，再往右移0，还是0，这样就可以很好的表示* 0 和* 1
如下

1
2
3
4
5
6
int conditional(int x, int y, int z) {
  x=!x;
  x=x<<31;
  x=x>>31;
  return (y&~x)+(z&x);
}

8.x<=y返回1，否则返回0

两种情况：
1.x==y
2.x!=y 这种情况有好几种判断，最开始是总的1判断，用y-x判断符号位(理论上y>x,y-x,的符号位为1，但是0-0x80000000符号位为1，所以要加一个判断正负)
此时还有一种情况没考虑到，就是y<0,x>0时，再加一个判断条件就可以了

1
2
3
4
5
6
7
8
9
10
11
int isLessOrEqual(int x, int y) {
   int temp=!(x^y)&1;//判断相等 
   	printf("%d ",temp);
    temp=temp | !((y+(~x)+1)>>31);//判断大小
    printf("%d ",temp);
    temp=temp | ((x>>31)&~y>>31);//判断正负
   	printf("%d ",temp);
	temp=temp & !(y>>31&~(x>>31)&1);
	printf("%d ",temp);
   return temp;
}

9.实现!运算符

原理是~ 0 + 1 = 0,0取相反数还是0，符号位还是0，而别的数符号位为1，0或1，1的组合

1
2
3
int logicalNeg(int x) {
 return ((x>>31)&1|((~x+1)>>31)&1)^1;
}

10.返回x用补码表示的最小位数

这个题我初步的思路是有了，但是怎么不超过Max ops，我没想到……
看c部分就很容易理解了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int howManyBits(int x) {
	int s,c1,c2,c3,c4,c5,c6;
	int cnt = 0;	// 	计数
	s = (x>>31)&1;	//	符号位
	x = ((s<<31)>>31) ^ x; // 取反x
	s = !!(x>>16);	// 判断高16位是否有1，有则s为1
	c1 = s<<4;		// 若高16位有1，则低16位可以计数16
	x >>= c1;		// 右移将已经计数的位移除，c1若为0，则用折半的长度判断
	s = !!(x>>8);	// 用8位的长度去判断，有效位的个数计入c2
	c2 = s<<3;
	x >>= c2;
	s = !!(x>>4);	// 用4位的长度去判断，有效位的个数计入c3
	c3 = s<<2;
	x >>= c3;
	s = !!(x>>2);	// 用2位的长度去判断，有效位的个数计入c4
	c4 = s<<1;
	x >>= c4;
	s = !!(x>>1);	// 用1位的长度去判断，有效位的个数计入c5
	c5 = s;
	x >>= c5;
	c6 = !!x;		// 判断最低位是否为1
	cnt = c1+c2+c3+c4+c5+c6+1;	// 将每次获得的低位有效位相加，再加1位符号位
	return cnt;
}

11.返回2* f(浮点数)

这个题写了一两天人麻了，
关于浮点数，float的话，1位表正负(s)，8位表示阶码(e)，还有23位表示小数位(f)

  • 2有三种情况:
    1.返回它本身，如NaN,0,1<<31……
    2.是e部分* 2
    3.小数位* 2(e部分为0)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    unsigned floatScale2(unsigned uf) {
      unsigned s=((uf>>31)<<31);
      unsigned v=(0x1ff)<<23;
      unsigned temp=uf<<1;
      temp=temp>>24;//temp 表示 e
      unsigned var=uf<<9;//var 表示 小数位
      if((temp==255&&(((var>>31)&1)==1||var==0))){
      		return uf;//判断NaN的情况，以及0x7f800000
      }
      else{
    	  if(var==0){//小数位为0
    	  	  if(temp==0) //判断1000   0000 …… 0000
    			return uf;  
    	  	  temp+=1;//*2
    		  temp=temp<<23;
    		  return temp|s;//符号位
          }
      	  else{
      	  	if(temp==0){//exp为0
    			return 2*uf|s;//82
    		}
      	  	return (((temp+1)<<23)+(var>>9))|s;//exp不为0,小数位不变
    		}
      	  
      }
    }

12.返回int(float)

感觉上面那个题能写出来，这个也能写出来
float返回int，主要就是超出范围，还有NaN，返回0x80000000,然后根据exp部分的大小计算就可以了
并且exp部分最大为(规范化数)，511，当 511 - 256 ( 2 * 7 - 1 ) >= 32 时，int就无法表达了，这时
需要返回0x80000000,而属于int范围中的数直接将temp转化成整数，大于127再算2^temp就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int floatScale2(unsigned uf) {
  unsigned s=uf>>31;
  unsigned v=(0x1ff)<<23;
  unsigned temp=uf<<1;
  temp=temp>>24;
  unsigned var=uf<<9;
  int re=temp;
  int count=0;
  int result=1;
  if(re==0)
	return 0;
  else{
  	if(re==255)
  		return 1<<31;
  	else{
  		re-=127;
  		if(re<0)
  		return 0;
		if(re>=32)
		return 1<<31;
  		while(re>0){
  			result*=2;
  			re--;
		  }
		  if(s==1){
		  	return result*-1;
		  }
		  else return result;
  		
	}
  }
}

13.返回x的x次方

我理解的题目的意思是通过exp部分来实现2的x次方，但是x为负数返回0，感觉很奇怪，而且我本地还打不通，不能返回0
，太离谱了，思路很简单

1
2
3
4
5
6
7
8
9
unsigned floatPower2(int x) {
    unsigned INF = 0xff << 23;
	int e = 127 + x;
	if (x < 0)
		return 0;
	if (e >= 255)
		return INF;
	return e << 23;
}

最后得分28分，就差两个题……