【读书笔记】CSAPP ch2

第二章 信息的存储和表示

信息存储

十六进制表示法

(略)

字数据大小

  • 大多数计算机使用8bit的块(字节)作为最小的可寻址的内存单元
  • 字长指明了指针数据的标称大小(?)
  • 64位系统和32位系统向后兼容
  • C语言中有些数据类型的具体大小依赖于程序的编译,C99引入int32_tint64_t类型,指明数据的长度
  • C标准对不同数据类型的数字的范围设置了下界,没有设置上界

寻址和字节顺序

  • 存储规则:对象的地址是什么?在内存中如何排列这些字节?
  • 地址:多字节对象的存储地址为连续字节序列的最小字节地址
  • 排列方式:
    • 小端法:低字节存在低地址
    • 大端法:低字节存在高地址
    • 默认规则:书写时,地址从左往右表示从低到高,字节从左往右表示从高到低

【读书笔记】CSAPP ch2

  • 关心字节顺序的场合:
    • 网络数据传输
    • 阅读字节序列
    • 规避正常的类型系统,比如强制类型转换或者联合允许一种数据类型引用一个对象
  • 代码示例:按字节读取内容
//按照字节打印数据中的内容
#include<bits/stdc++.h>
using namespace std;
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, int len){
    int i;
    for(i = 0; i < len; ++i){
        printf(" %.2x", start[i]);
    }
    printf("\n");
}
void show_int(int x){
    show_bytes((byte_pointer)&x, sizeof(int));
}
int main(){
    int num;
    cin >> num;
    show_int(num);
    return 0;
}

字符串的表示

  • 用ASCII码表示
  • ASCII码只能表示英文字符,更一般的字符采用Unicode

代码表示

  • 二进制代码不兼容,即不同系统上编译得到的二进制代码不同

布尔代数

  • 运算:与、或、非
  • 位向量
  • 位向量表示有限集合

C语言中的位运算

  • 将十六进制转换为二进制执行二进制运算,然后将结果转换为十六进制

C语言中的逻辑运算

  • 0表示false,非0表示true
  • 与位运算的不同:
    • 位运算的参数是0或1
    • 逻辑运算有短路原则

C语言中的移位运算

\([x_{\omega - 1}, x_{\omega - 2}, ..., x_0]\)

  • 左移:高位舍弃,低位补0 $ [x_{\omega - 1 - k}, x_{\omega - 2 - k}, ... x_0, \underbrace{0, \cdots, 0}_{k个}]$
  • 右移:
    • 算数右移:补符号位 \([\underbrace{x_{\omega - 1}, ..., x_{\omega -1}}_{k个}, x_{\omega -1}, x_{\omega - 2}, ..., x_k]\)
    • 逻辑右移:补0 \([\underbrace{0, ..., 0}_{k个}, x_{\omega - 1}, ..., x_k]\)

整数的表示

整型数据类型

  • 典型实现中,负数比正数多1个
  • C语言标准中规定(1)固定了数据大小(2)正数和负数对称

数据编码

假设整型数据类型有\(\omega\)位,将其表示记作位向量\(\vec x = [x_{\omega - 1}, x_{\omega - 2}, \cdots, x_0]\)

无符号数编码

  • 定义:

\[ B2U_{\omega}(\vec x)=\sum_{i=0}^{\omega - 1} x_i 2 ^ i \]

  • 范围:\(Umax = \sum\limits_{i = 0}^{\omega - 1} 2 ^ i = 2 ^\omega -1\)

  • 示例:

【读书笔记】CSAPP ch2

  • 定理:\(B2U_\omega(\vec x)\)是一个双射

补码表示

  • 定义:
    \[ B2T_{\omega}(\vec x) = -x_{\omega - 1}2^{\omega - 1} + \sum_{i = 0}^{\omega - 2}x_i 2 ^i【注】补码表示中,最高位被理解为负权 \]
    【注】补码表示中,最高位被理解为负权

  • 范围:\(Tmin = -2^{\omega - 1}, Tmax = \sum\limits_{i = 0} ^ {\omega - 2}2 ^ i = 2 ^{\omega - 1} - 1\)

  • 示例:

    【读书笔记】CSAPP ch2

  • 定理:\(B2T_\omega(\vec x)\)是一个双射

【注】

  • 补码的范围中:\(\vert Tmin\vert = \vert Tmax\vert + 1\)
  • 补码和无符号数:\(Umax = 2Tmax + 1\)

  • 所有机器都将有符号数表示为补码,尽管C语言标准没有明确规定

反码表示

  • 定义:
    \[ B2O_{\omega}(\vec x) = -x_{\omega - 1}(2^{\omega - 1} - 1) + \sum_{i = 0}^{\omega - 2}x_i2^i \]

原码表示

  • 定义:

\[ B2S_\omega(\vec x) = (-1)^{x_{\omega - 1}}\times \sum_{i = 0}^{\omega - 2}x_i2^i \]

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

  • C语言强制类型转换:不改变位级表示,只改变位的解释方式

补码转无符号数

  • 补码转为无符号数:
    \[ T2U_\omega(x) = \begin{cases} x + 2 ^\omega & x < 0,\x & x \geq 0 \end{cases} \]

  • 推导:

\[ \begin{align} B2U_\omega (\vec x) - B2T_\omega(\vec x) &= x_{\omega - 1}2^\omega \Longrightarrow B2U_\omega(\vec x) = x_{\omega - 1}2^\omega + B2T_\omega(\vec x)\T2U_\omega(x) &= B2U_\omega(T2B_\omega(x)) \&= x_{\omega -1}2^\omega + B2T_{\omega}(T2B_\omega)(x)\&= x_{\omega- 1}2^\omega + x \end{align} \]

  • 理解:将补码中最高位解释为负权变为解释为正权,将补码看做无符号数时,正数不变,负数变为一个更大的数
  • 示例:
    【读书笔记】CSAPP ch2

无符号数转补码

  • 转换:

\[ U2T_{\omega}(x) = \begin{cases} u & u \leq Tmax_\omega \u - 2 ^ \omega & u > Tmax_\omega \end{cases} \]

  • 推导(同补码转无符号数)

总结

【读书笔记】CSAPP ch2

C语言中的有符号数和无符号数的转换

  • C语言中默认数字都是有符号
  • 声明一个无符号常量需要在数字后面缀上‘U’
  • 一个运算中同时出现有符号数和无符号数时,会被隐式转换为无符号数

扩展数字的位表示

无符号数的0扩展

  • \(u_\omega = [u_{\omega -1}, \cdots, u_0]\longrightarrow u'_{\omega + k} = [\underbrace{0, \cdots, 0}_{k个}, u_{\omega -1}, \cdots, u_0]\)

补码的符号扩展

  • 定义

\[ x_\omega = [x_{\omega - 1}, \cdots, x_0]\longrightarrow x'_{\omega + k} = [\underbrace{x_{\omega-1}, \cdots, x_{\omega - 1}}_{k个}, x_{\omega - 1}, \cdots, x_0] \]

  • 推导
    \[ \begin{align} B2T_{\omega + 1}(\vec x') &= -x_{\omega -1}2^\omega + \sum_{i = 0}^{\omega - 1}x_i2^i\&= -x_{\omega - 1}2^\omega + x_{\omega -1}2^{\omega - 1} + \sum_{i=0}^{\omega - 2}x_i 2^i\&= -x_{\omega - 1}2^{\omega -1}+\sum_{i=0}^{\omega - 2}x_i 2^i\&= B2T_\omega(\vec x) \end{align} \]

截断数字的位表示

无符号数的截断

  • 定理

\[ \vec x = [x_{\omega -1 }, \cdots, x_0], \vec x' = [x_{k-1}, \cdots, x_0]\x' = x \mod 2^k \]

  • 推导:截断的部分对应的位权为\(2^{k}, \cdots, 2^\omega\)

补码的截断

  • 定理

\[ \vec x = [x_{\omega -1 }, \cdots, x_0], \vec x' = [x_{k-1}, \cdots, x_0]\x' = U2T_k(x\mod 2^k) \]

  • 推导:以无符号数为中介

整数的运算

无符号数加法

  • 定义运算\(+_\omega^u\),将无符号数\(x, y\)相加后截断\(\omega\)位,可以视作是一种模运算
  • 无符号数加法:

对于满足\(0\leq x, y < 2^\omega\),有:
\[ x+_\omega^u y = \begin{cases} x + y & x + y < 2 ^ \omega \x + y - 2 ^ \omega & x + y \geq 2 ^\omega \end{cases} \]

【读书笔记】CSAPP ch2
【读书笔记】CSAPP ch2

  • 溢出判断:对于\(s = x+_\omega^uy\),当且仅当\(s < x\quad or\quad s < y\)时发生溢出
  • 无符号数求反:模数加法形成了一个阿贝尔群,定义\(x\)的反为:

\[ -_\omega^u x = \begin{cases} x & x = 0\2^\omega - x & x > 0 \end{cases} \]

补码加法

  • 定义运算\(+_\omega^t\),将有符号数\(x, y\)相加后截断\(\omega\)位,可以视作是一种模运算
  • 补码加法:

\[ x+_\omega^t y=\begin{cases} x+y-2^\omega & 2 ^{\omega - 1} \leq x + y\x+y & -2^{\omega -1 } \leq x + y < 2 ^{\omega -1}\x+y+2^\omega &x + y < -2^{\omega -1} \end{cases} \]

【注】还是来源于截断,当没有溢出时,不发生截断;溢出的情况只会是“正+正”或者“负+负”;“正+正”溢出时,符号位为0,数字部分的最高位变为1(进位导致增加的数字),截断后原有的符号位会被丢弃,符号位变为1,真实的值为\(x+y=2^{\omega -1} + \sum\limits_{i=0}^{\omega -2}x_i2^i\),截断后的值为\(x+_\omega^t y- = 2^{\omega -1} + \sum\limits_{i=0}^{\omega -2}x_i2^i\),因此\(x+_\omega^t y = x + y - 2^\omega\);负溢出解释相似。

【读书笔记】CSAPP ch2

【读书笔记】CSAPP ch2

  • 推导:

有符号和无符号具有相同的位级表示,因此先将参数转换为无符号数,然后按照无符号数运算,最后将结果转换为补码
\[ \begin{align} x+_\omega^u y &= U2T_\omega(T2U_\omega(x) + T2U_\omega(y))\&= U2T_\omega((x_{\omega-1}2^\omega + y_{\omega - 1}2^\omega+x+y)\mod 2^\omega)\&= U2T_\omega((x+y)\mod 2^\omega) \end{align} \]
\(z=x+y, z' = z\mod 2^\omega, z'' = U2T_\omega(z')\)

\(-2^{\omega}\leq z < -2^{\omega-1}\),则\(z'=z+2^\omega\),因此\(0\leq z' < 2^{\omega -1}\),故\(z''=z'\)

其余三种情况以此类推

  • 补码加法溢出判断:“正+正=负”或者“负+负=正”

补码的非

  • 定义:对于满足\(Tmin\leq x \leq Tmax\)\(x\)

\[ -_\omega^tx=\begin{cases} Tmin &x = Tmin\-x & x>Tmin \end{cases} \]

  • 根据位级表示计算补码的非:
    • 各位取反再加1:-5=[1011], [0100] + [0001] = [0101] = 5
    • 将符号位(包含符号位)与最后一个1之间的位取反:5=[0101], [1011] = -5

无符号乘法

  • 定义:\(x*_\omega^uy=(xy)\mod 2^\omega\)

补码乘法

  • 定义:\(x*_\omega^t y=U2T_\omega({(xy)\mod 2^\omega})\)
  • 无符号和补码乘法的位级等价性

给定长度为\(\omega\)的位向量\(\vec x, \vec y\),用补码形式定义的整数为\(x, y\),用无符号定义的整数为\(x', y'\),则:
\[ T2B_\omega(x*_\omega^t y) = U2B_\omega(x'*_\omega^u y') \]

证明
\[ \begin{align} (x'*y')\mod 2^\omega &= ((x_{\omega -1}2^\omega+x) \cdot (y_{\omega -1}2^\omega + y))\mod 2^\omega\&= (xy)\mod 2^\omega\T2U_\omega(x*_\omega^t y)&=T2U_\omega(U2T_\omega((x\cdot y)\mod 2^\omega))\&= x\cdot y \mod 2^\omega\T2B_\omega(x*_\omega^t y)&=U2B_\omega(T2U_\omega(x*_\omega^t y))\&=U2B_\omega((x\cdot y)\mod 2^\omega) \end{align} \]

乘常数

  • 乘2的幂:\(x\cdot 2^k = x << k\)
  • 乘以常数K:将常数K分解为{0,1}序列,然后通过移位和加法
  • 计算\(x\cdot K\)
    • 分解K:\(K = [(0...0)(1...1)(0...0)...(1...1)]\)
    • 计算:考虑从\(n\)位到\(m\)位(\(n \geq m\))为连续的1,有两种计算方案:
      • \((x<<n) + (x <<(n-1))+...+(x<<m)\)
      • \((x<<(n+1)) - (x<<m)\)

除以2的幂

  • 对于无符号数,\(x>>k\)产生数值\(\lfloor x/2^k\rfloor\)

  • 对于有符号数

    \(x>0\)时同无符号数

    \(x<0\)时,\(x>>k\)产生数值\(\lfloor x/2^k\rfloor\)\((x+(1<<k) - 1)>>k\)产生数值\(\lceil x/2^k\rceil\)

  • 偏置的设计:

    注意到$\lceil x/y\rceil = \lfloor (x+y-1)/y\rfloor \(,设\)x = qy+r\(,因此\)\lfloor (x+y-1)/y\rfloor=q+\lfloor(r+y-1)/y\rfloor\(,当\)r\(为0时,后面一项为0,当\)r>0\(时后面为1。取\)y=2^k$,即可得到带偏置的除法公式

【读书笔记】CSAPP ch2

上一篇:php学习系列之-eclipse的xdebug使用


下一篇:simple go web application & 二维码生成 & 打包部署