csapp第二章 信息的处理和表示(2)

布尔代数

弄清楚布尔代数的运算和逻辑运算以及离散数学中的命题逻辑的一一对应关系。

位向量

固定长度为w，由0和1组成的串

位向量的运算可以对应为参数的每个对应元素的运算

任意a a^a=0

位向量表示有限集合，则布尔运算& 和|对应集合的交并

c语言中的位级运算

位级运算的常见用法是实现掩码运算，掩码是一个位模式，表示从一个字中选出的位的集合

x&0xFF生成一个由最低有效字节生成的值，其他的字节被置为0

求补时要想到利用异或运算 对1异或可得其补，对0异或可得本身 见p39练习12

c中的逻辑运算

c中的逻辑运算符|| && ！ 对应命题逻辑中的OR AND NOT 注意区分逻辑运算和位级运算

  1. 第一个区别 逻辑运算所有非0参数都表示为true 参数0才表示false ，按位运算只有在参数被限制为0或1时才和对应的逻辑运算有相同的行为
  2. 第二个区别 如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符不会对第二个参数求值

c中的移位运算（x<<k）(x>>k)

左移：向左移动k位，丢弃最高的k位，在右端补k个0

逻辑右移：在左端补k个0，右移k位（无符号数必须逻辑右移）

算术右移：在左端补k个最高有效位的值

java中

x>>k会将x算术右移k个位置

x>>>k会对x做逻辑右移

整数表示

书中记述的比较详细，这里仅列出一部分要点

整型数中无符号数的编码，了解函数B2Uw（x的位模式）

补码编码的方式，了解函数B2Tw（x的位模式）

​ 补码运算的一些特殊地方，0表示2非负数，所以最高位是1的数会比最高位是0的数多一个 ，也就是负数会比正数多一。

有符号数和无符号数之间的转换：

​ 强制类型转换结果保持位值不变，仅仅改变解释这些位的方式

换句话说，同一个数据，只是解读方式不同 。 补码和无符号数之间的关系，举例16位位模式0xCFC7的补码表示是-12345，无符号表示位53191，而两者绝对值相加得到65536=2的16次方。

补码转换为无符号数，使用函数T2Uw(x)

x<0时，函数值为x+2^w

x>0时，函数值为x

无符号数转换位补码,调用函数U2Tw(u)

u<=TMaxw，函数值为u

u>TMaxw，函数值位u-2^w

扩展一个数字的位表示

对于一个无符号数转为更大的数据类型只需要简单地在表示的开头添加0，这种运算称为零扩展

对于有符号的数，即补码进行符号扩展(sign extension)，就是添加最高有效位的值

整数运算

无符号加法

x+y=(x+y)mod2^k`

溢出会舍去

阿贝尔群，群论。

补码加法

大多数计算机使用同样的机器指令来执行有符号和无符号之和。

img

x（有符号+）y= U2T（T2U（x+y) mod 2^w)

  • 先计算x+y
  • 将x+y转换为无符号类型z。
  • p=z mod 2^w
  • 附.(或者直接对x+y的二进制表示进行截断得到p)

  • 将p用有符号类型表示

  • 正溢出，正常，负溢出。

    img

img

补码的非

  • 因为正负区间的不一致
  • 所以最小的那个负数的相反数逆元还是最小的那个负数。
  • 对于任意整数x。-x和~x+1得到的结果完全一样。

无符号乘法

只取低w位表示的值，其余截断

补码乘法

对于无符号和补码乘法，乘法运算的位级表示都是一样的，是同一条指令。无符号和补码相乘出来的两个数的低W位 永远相等。证明见书。

img

乘常数

因为乘法速度太慢，机器可能会用（加法，减法，移位）来代替乘法。

img

除以2的幂

对于无符号类型或整数，直接右移不会有任何问题。

对于负数，最后的值为-48.3，会舍入成 -49，而不是-48.

浮点数

一个二进制串分为三部分。

  1. 符号位，1位，决定正负。
  2. 阶码 E，对浮点数加权，2^E。C语言里float，8位；double, 11位。
  3. 尾数 M，二进制小数，计算分情况。C里float, 23位；double, 52位。

计算根据阶码分为三种，规格化、非规格化、特殊值，float为例：

  1. 规格化，E各位不全为0也不全为1，即e!=0 && e!=255。E = e - 127。所以E的范围其实是[-126, 127] 。此时 M = m + 1。所以最后绝对值为 M·2^E = (m+1)·2^(e-127)。
  2. 非规格化，全为0，e=0。E = 1 - 127. M = m。所以最后绝对值为 M·2^E = m·2^(-126)。当m取最小值2^(-23)时，这也是float能够表示的最小非零数，2^(-149)。
  3. 特殊值，全为1，e=255。当m=0时，根据符号位分别得到+∞和-∞。当m!=0时，得到NaN，意为 Not a Number。

至于为什么e=0时，M=m而不是M=m+1？
此处结合e=0时，E也不是0-127，而是1-127,正好等于规格化的最小e，也是1-127。这个在非规格化向规格化过渡的时候，相同的指数值，保证整个f的值会随着m的增长而增大（线性的）。因此，对浮点数排序时，也可以像整数一样，直接比较其二进制位，从高位开始比较。

这个设计很有意思，假如在非规格化时，E=0-127，M=1+m，非规格化最大数为E=-127,M=1+(2^23-1)/2^23，f=2^E·M=2^(-126)-2^(-150)。规格化最小数为E=1-127，M=1+0，f’=2^(-126)。（哎？f’>f，额这是哪里算错了吗？）f’-f=2^(-150).

真实情况是，非规格化最大数为E=1-127，M=(2^23-1)/2^23，f=2^(-126)-2^(-149)，规格化最小数仍然是f’=2^(-126).f’-f=2^(-149)。这正是相邻的两个非规格化数的间隔2^(-126)·2^(-23)=2^(-149)。也就是说IEEE的这种设计保持了在非规格化和规格化数之间的一个平滑过渡。

​ 强转与舍入

  • int转为float，不会溢出，但是可能被舍入，毕竟都只有2^32个状态，能表达的总信息量是一定的。如2^24+1和2^24强转为float后，值为2^24.000000。舍入的时候会有一种特殊情况，称为向偶数舍入，在非有效位值正好是两个可能值的中间值时，我们倾向于通过取舍，使得有效位的最后一位为0.
  • double转float, 可能溢出为-∞或+∞.
  • float和double转int，向零舍入。如果出现溢出，则值会变成0b1000 0000，也就是-Min。