cs_learn

十六进制与二进制，十进制转换(手动)

关于十六进制转成二进制:一个窍门是:记住十六进制的A对应十进制的10，以此类推到十六进制的F对应十进制的15.然后把十六进制的每一位用对应的十进制代替，再将十进制写成二进制，即为十六进制对应的二进制。

对于当一个十进制数是2^n n为整数时，可以把n表示成i+4j ,其中0<=i<=3 ,那么这个十进制数可以直接写成对应的十六进制:0x2^i 后面+j个0.例如:十进制下:2的11次方，n=11=3+4*2 ，可以直接写成十六进制:0x800.

而对于十六进制与十进制的转换,可以用短除法和乘法

两种顺序存储字节的方法

• 大端法:最高有效字节在最前面 (跟手写数字一样)
• 小端法:最低有效字节在最前面 (刚好相反)

布尔代数

对于二进制表示|位向量:[01101001] 来说，表示集合中含有的元素是0,3,5,6.使用这种编码集合的方法时，布尔运算| 对应集合的并,& 对应集合的交,~ 对应集合的补.

对于十六进制数地位级运算，先将十六进制数的各个参数扩展成对应的二进制表示，然后再做二进制运算，最后转回十六进制。

逻辑运算

||,&&,!，对应命题逻辑的OR,AND,NOT.

逻辑运算认为所有非零参数都表示true,参数0则表示FALSE.

短路效果:对于逻辑运算，如果第一个参数就能确定表达式结果，就不会对之后的参数进行运算。

移位运算

• x<<k:左移k位,丢弃最高k 位,并在右端补k个0.从左往右可结合:x<<k<<j==(x<<k)<<j

• 逻辑右移:Java 用x>>>k:在左端补k个0.

• 算术右移:x>>k表示.在左端补k个最高有效位的值.

移位运算的优先级比+ -运算低

整数表示

• 无符号数编码定义:\(B2U_w(\overline x)=\sum_{i=0}^{w-1}x_i2^i\)

• 补码编码定义:把无符号数的最高位变成符号位:即最高位的符号是-,其余位不变

处理同样字长的有符号数和无符号数之间的转换:数值可能改变，但位模式不变.

扩展位表示

• 无符号数的零扩展
• 补码数的符号扩展

截断

• 无符号数的截断
• 补码数的截断

运算

• 加法
  • 无符号加法
    • 正常 x+y
    • 正溢出 x+y-(1<<w)
  • 补码加法
    • 正溢出 x+y-(1<<w)
    • 正常 x+y
    • 负溢出 x+y+(1<<w)

检测无符号溢出:如果x+y的结果s<x||s<y

检测补码溢出:

​ 1.正溢出,x>0,y>0但x+y的结果s<=0;

​ 2.负溢出:x<0,y<0但s>=0。

计算位级补码的非表示

一: 对每一位求补,再对结果+1

二: 设存在一位k(k是下标),k是最右边1 的位置,对k左边的所有位取反.

• 乘法
  • 无符号乘法: (x*y)mod (1<<w)
  • 补码乘法:
    • 首先跟无符号乘法一样先取模,然后计算无符号转换补码

2的幂:

​ 1<<k: 表示* 2的k次幂

​ 1>>k: 表示/ 2的k次幂

无符号运算和补码运算乘以2的幂都可能会溢出，但是即便溢出，通过移位得到的结果是一样的。如11 的二进制4位[1011],11<<2=44,即[101100]截断为4位[1100]十进制为12==44 mod 16

浮点数

定点表示

每个十进制小数可以根据小数点的位置，分割成左右两部分。左边的数字用10的正幂表示，右边则是负幂。

二进制小数的表示也是类似的

但在有限长度编码里面，十进制不能准确表示无限小数，同理有些小数在二进制表示里面只能取到近似值。

IEEE 浮点表示

IEEE 标准使用V=(-1)^s * M * 2^E的形式表示一个数

• 符号（sign） s 决定v的正负
• 尾数M 是一个二进制小数
• 指数 E 对浮点数加权
• 阶码 e
  • 单独的符号位s
  • k位的阶码字段exp
  • n位小数字段frac

规格化:exp 的位模式不全为0 也不全为1。指数值:E=e-Bias,尾数定义为M=1+f,f 为小数字段frac描述的小数值

非规格化:阶码域全为0.指数值E=1-Bias,尾数值M=f

特殊值：- 无穷大 - NaN (Not a Number)

浮点运算

• 浮点加法不可结合
• 浮点加法满足单调性
• 浮点乘法可交换
• 浮点乘法不可结合
• 浮点乘法不具备分配性