Lecture 01:Bits,Bytes and Integer

大端法与小端法

对于0x01234567，最高有效为0x01，最低有效位为0x67

大端法：

小端法：

Windows，Linux采用小端法

Bool代数

&：按位与，|：按位或，^：按位异或，~：取反

&&：与，||：或，！：非

移位运算：

$x«k$，$x$向左移动$k$位，丢弃最高的$k$位，并在右端补$k$个0。

算术右移：$x»k$，$x$向右移动$k$位，丢弃最低的$k$位，并在左端补$k$个最高有效位。

逻辑右移：$x»k$，$x$向右移动$k$位，丢弃最低的$k$位，并在左端补$k$个0。

无符号数的编码

$B2U_w(x)$=$$\sum_{i=0}^{w-1}{x_i2^i}$$，$w$表示数$x$的位数

$B2U_4([1010])=12^3+02^2+12^1+02^0$=10

无符号数编码的唯一性，函数$B2U_w$是一个双射。

补码编码

$B2T_w(x)=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}{x_i2^i}$，$w$表示数$x$的位数

$B2T_4(1011)=-12^3+02^2+12^1+12^0=-8+0+2+1=-5$

补码编码的唯一性，函数$B2T_w(x)$是一个双射。

有符号与无符号数的转换

$$T2U_w(x)=\begin{cases} x+2^w,x<0\x,x≥0\end{cases}$$

$$U2T_w(u)=\begin{cases} u,u≤TMax_w\u-2^w,u＞TMax_w\end{cases}$$

强制类型转换，只是改变了位的解释方式，不改变位值。

扩展一个数字的位表达

无符号数的零拓展

宽度为$w$的位向量$u=[u_{w-1},u_{w-2},···，u_0]$，

宽度为$w^的位向量u^=[0,0,u_{w-1},u_{w-2},···,u_0]，$其中$w^`＞w$.

补码数的符号拓展

宽度为$w$的位向量$u=[u_{w-1},u_{w-2},···，u_0]$，

宽度为$w^的位向量u^=[u_{w-1},u_{w-1},u_{w-1},u_{w-2},···,u_0]$，其中$w^`＞w$.

截断

将数从高位向低位强制转换时，会发生截断，截断$k$位，即丢弃其高$k$位。即，虽然原地址储存的数据没有变化，但是其高k位已经没有了意义。

例如，int转short。

整数运算

无符号数加法

$$x+y^u_w=\begin{cases} x+y,x+y＜2^w\x+y-2^w,2^w≤x+y<2^{w+1}\end{cases}$$

无符号求反

$$-x^u_w=\begin{cases}x,x=0\2^w-x,x>0\end{cases}$$

补码加法

$$ x+y^t_w=\begin{cases} x+y-2^w,2^{w-1}≤x+y\x+y,-2^{w-1}≤x+y<2^{w-1}\x+y+2^w,x+y<-2^{w-1}\end{cases} $$

补码的非

$$ -x^t_w=\begin{cases}TMin_w,x=TMin_w\-x,x>TMin_w\end{cases} $$

无符号的乘法

$$ x*y^u_w=(x·y)mod 2^w $$

补码的乘法

$$x*y^t_w=U2T_w((x·y)mod 2^w)$$

与常数的运算

对于任意常数的运算在后面会讲，类似进行$(a«k)+b$,例如$(a«1)+a=3*a$

现在主要考虑与2的幂的运算：

乘法：

实际就是对其二进制表示进行左移操作，对于固定字长的数需要舍弃超出的位数。

除法：

实际是进行右移操作，对于无符号数进行逻辑右移，而对于补码，为了保持其符号的一致，进行的是算术右移。

这也解释了为什么右移有两种，而左移只有一种。

对于补码除法还有一个舍入问题，看下面的例子：

执行表达式$x»k$

可以发现进行算术右移后，结果进行了向下舍入，而不是向零舍入。这使我们的数产生了很大的偏差，所以我们使用“偏置（biasing）”来进行修正：

执行表达式$(x+(1«k)-1)»k$