计算机系统漫游

pc:一个字(word)的空间,存储某一指令的地址
- 32bit system:1 word=4 bytes
bus:总线

进程
- 上下文:操作系统跟踪的进程运行所需要的所有信息
虚拟内存(为每个进程提供了巨大的连续地址)
使用ssh运行程序
提高运行速度:
- 线程级并发(thread-level concurrency)
- 指令级并行(instruction-level parallelism)
- 单指令多数据并行(single instruction multi data parallelism)

超线程：一个cpu执行多个线程(cpu中部分硬件是有备份的)，常规切换线程很慢,超线程可以决定并很快切换线程

程序结构和执行

第二章

信息的表示和处理(book)

进制转换:十六进制每一位换成四位的二进制,二进制每四位算出十六进制
位运算:取补<=>异或上全1的掩码
- x&~0xff:取最低位的字节
- 区分:c语言的逻辑运算符和位运算(~和!)
- 左移位就是直接补0,逻辑右移补零,算术右移补最高位(c标准没规定,但是基本上都是有符号数算数右移,无符号就是逻辑)
补码(two’s complements)(最高位解释为负权)
- binary_to_two’s= $-x_{\omega-1}2^{\omega-1}+\sum_{t=0}^{\omega-2}x_i2^i$
- 特殊:-1和无符号的最大整数具有相同表示
- c标准仅规定了最低要求，所以可移植性没有java好
- e.gprintf("x=%" PRId32 ",y=%" PRIu64 "\n",x,y);可根据宏展开
- 有符号数和无符号数的转换:位表示不变,对于在0~有符号最大值之间的数保持不变,之外的需要加上或减去 $2^{\omega}$
- c语言中表达式有无符号数就先变成无符号再算,有符号最小值:-INT_MAX-1
扩展一个数字的位表示(从小到大)
- (无符号数)零扩展:直接在最前面加0
- (有符号数的补码表示)符号扩展:最前端补最高有效位
- 位转换和有无符号转换的先后顺序实际上会影响结果
截断数字
- 无符号: $x^{'}=x\text{ mol } 2^k$
- 补码: $x^{'}=U2T_k(x\text{ mol }2^k)$
整数运算
- 无符号加法:根本就是丢弃最高位,所以溢出的时候就是减去 $2^{\omega}$ $2^{ω}$
  - 检测溢出:当且仅当结果小于加数的时候
  - 无符号数求反(相加为0的元):0就是0,非零为 $2^{\omega}-x$
- 补码加法
  - 检测溢出:两正数和为负
  - 模数加法会形成阿贝尔群:可交换so x+y-x总是会得到y
  - 溢出相关:非对称所以总是应该把补码最小值作为边界考虑
  - 补码的加法逆元:除了TMIN之外都直接取相反数
  - 补码一般逆元:每一位取非再加1
    - tmin为其自己(实际上也满足)
- 乘法
  - 无符号:结果取模即可
  - 有符号:结果取模之后再U2T(两种乘法的最终位表示是一样的)
  - 二进制表示:乘以2的幂就是左移对应的位数x<<k,编译器常常将乘法优化为移位等

信息的存储

程序将内存视为极大字节数组(每个字节由地址表示,其集合称为虚拟地址空间)
位模式(通常的二进制太麻烦所以常用十六进制):
进制转换
机器兼容:32位程序通常可以在64位机器上运行

整数的表示及运算

无符号数
有符号数(补码)
- -1和无符号最大值的二进制表示相同
类型转换(位模式不变,解释方式变换,c语言会将有符号隐式转换为无符号)
扩展数字的位表示
- 无符号:直接补零即可
- 有符号:前面全部补上符号位
截断
- 无符号数:直接对 $2^k$ 取模(k为截断位数)
- 有符号数:先对其位表示使用无符号数表示,截断再转换回来
无符号溢出
- 有符号分正溢出和负溢出
- 有符号逆元:最小值的逆元是其本身
整数乘法:采用截断(位表示相同的数的乘积截断后的位表示相同)
- 乘操作很多时候会被编译器优化为移位与加减法表示
- 除法:为了保证除不尽的时候偏向0舍入

浮点数

二进制浮点:小数点后的权是2的负次幂

three type:
- 规格化的值(normalized)
- 非规格化的值(denormalized)
- 特殊值(special)
整数与浮点数的转换
- 因为这种表示有误差,所以舍入很重要:向上、向下、向零、向偶数(哪边近选那边,一样进选偶数那边)
  - e.g:10.11100舍入为11.00 (二进制中0为偶,10.11和11.00中选)

datalab

~(~(x&~y)&(~(~x&y))):非加并实现异或
判断最大值:x+1=~x当且仅当x为最大值或x为-1
- !(x+1^(~x))&(!!(x+1))

int mask = 0xAA | (0xAA << 8);
mask = mask | (mask << 16);
//显式拼接掩码,位数确定

int isAsciiDigit(int x) {
    int high = x & 0xF0;            // 高 4 位
    int low  = x & 0x0F;            // 低 4 位
    int low_check = ((low + 6) & 0xF0) ^ 0x10;  // 如果低 4 位 ≤ 9，高位不会进位
    return !(high ^ 0x30) & !(low_check);
}
//判断是否为asciidigit :0x30~0x39

int conditional(int x, int y, int z) {
  int flag=!!x;//zero for the false x
  int mask=~flag+1;
  return ((~mask)&z)|(y&mask);
}
//注意零一掩码的生成

int isLessOrEqual(int x, int y) {
  int obvious_true=(x&(1<<31))&(!(y&(1<<31)));//1 for true
  int obvious_false=(!(x&(1<<31)))&(y&(1<<31));//1 for false
  int judge=!(((~x+1)+y)&(1<<31));
  int obvious=obvious_true|(!(x^y));
  return (obvious|judge)&(!obvious_false);
}
//非零数:其与其逆元一定最高位异号
int logicalNeg(int x) {
  int neg=~x+1;//zero for x=0;
  return ~((x|neg)>>31)&1;
}

int howManyBits(int x) {
  int b16, b8, b4, b2, b1, b0;
  int sign = x >> 31;
  x = sign ^ x; // 如果x是负，则取反，如果x是正，则不变。

  // 查看高16位是否有1， 如果有1，则b16被置为 2^4
  b16 = (!!(x >> 16)) << 4;
  x = x >>
      b16; // 然后舍弃，如果高16位有，则不再使用低16位；如果高16位没有，则数字不变。下面同理。
  b8 = (!!(x >> 8)) << 3;
  x = x >> b8;
  b4 = (!!(x >> 4)) << 2;
  x = x >> b4;
  b2 = (!!(x >> 2)) << 1;
  x = x >> b2;
  b1 = (!!(x >> 1)) << 0;
  x = x >> b1;
  b0 = x;

  // 把位置转化为数字。
  return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

//浮点数乘法
unsigned floatScale2(unsigned uf) {
  unsigned sign=uf>>31;
  unsigned e=(uf>>23)&0xff;
  unsigned last=uf&0x7fffff;
  //case1:normalized
  if(e!=0&&e!=255){
    e+=1;
    if(e==0xff){
      last=0;
    }
    return sign<<31|e<<23|last;
  }else if(e==0){
    last=last<<1;
    return sign<<31|e<<23|last;
  }else{
    return uf;
  }
}

//移位次数不能为负
//左移三十一位对int来说可能未定义
int floatFloat2Int(unsigned uf) {
  unsigned sign=uf>>31;
  unsigned exp=(uf>>23)&0xff;
  unsigned frac=uf&0x7fffff;
  int e=exp-127;
  int result;
  int s=(sign==0?1:-1);
  int m=(1<<23)|frac;
  if(exp==0|e<0)return 0;
  if(exp==255|e>30)return 0x80000000u;
  if(e>23){
    result=m<<(e-23);
  }else{
    result=m>>(23-e);
  }
  
  return result*s;
}

unsigned floatPower2(int x) {
  unsigned sign=0;
  unsigned exp,frac=0;
  unsigned pos;
  if(x<=-150)return 0;
  if(x>=128)return (0xff<<23);
  if(x>=0){
    exp=x+127;
  }else{
    if(x<-126){
      exp=0;
      frac=1<<(23-(x+126)*(-1));
    }else{
      exp=x+127;
    }
  }
  return sign|(exp<<23)|frac;
}

csapp_datalab

计算机系统漫游

程序结构和执行

第二章

信息的表示和处理(book)

信息的存储

整数的表示及运算

浮点数

datalab