CSAPP 2021-01-18

发表于 2021-01-18 更新于 2025-02-14 分类于组成原理阅读次数： 1

此文章的 撰写时间 可能有误

CSAPP Today 2021-01-18

一左移和右移

对于x<<k称为将 $x$ 左移 $k$ 位。对于一个位向量表示为 $[x_{w - 1}, x_{w - 2}, . . ., x_{0}]$ 的操作数 $x$ , x<<k的结果是 $[x_{w - k - 1}, x_{w - k - 2}, \dots, x_{0}, 0, \dots, 0]$ 也就是向左移动 $k$ 位, 右侧空缺用0补齐。在C中，左移运算符从左至右结合。即x<<i<<j相当于(x<<j)<<k

对于x>>k成为将 $x$ 右移 $k$ 位。不同的是，右移有两种形势，算术右移和逻辑右移。

1.1 逻辑右移

逻辑右移与左移相对，即对于一个位向量表示为 $[x_{w - 1}, x_{w - 2}, . . ., x_{0}]$ 的操作数 $x$ , x<<k的结果是 $[0, . . ., 0, x_{w - 1}, x_{w - 2}, . . ., x_{k}]$ 也就是说，向右移动 $k$ 位，抛弃最右侧的k位，在左端补0

1.2 算术右移

与逻辑右移不同的是，同样是抛弃最右侧k位，但在左端补原数的最高有效位，即对于一个位向量表示为 $[x_{w - 1}, x_{w - 2}, . . ., x_{0}]$ 的操作数 $x$ , x<<k（算术右移）的结果是 $[x_{w - 1}, x_{w - 1}, . . ., x_{w - 1}, x_{w - 2}, . . ., x_{k}]$

大多数C编译器使用算术右移。但对于无符号数除外，因为无符号数只能逻辑右移。 Java标准明确规定执行逻辑右移。

Tips:

UB (Undefined Behavior) 是指C或C++标准并未定义的语法，这通常意味着编译器可以在遇到ub时做任何事，比如打开一个游戏 ~~我在某个群听到说古老版本的g++碰到ub就是打开一个游戏~~

那么为什么要有ub呢？是因为制定标准的人没想到吗？为什么java没有ub呢？

大家知道C和C++是偏向底层的语言，追求速度（即便C++有OOP 模板元等特性，但也追求零开销抽象）而对于不同情况，留下一些“漏洞”让编译器自行决定在某些特定场合 ~~比如造火箭~~ 可以追求到极致速度而Java则没有这样的问题，毕竟JVM上的东西就算没有GC也不可能满足某些场景下的苛刻条件的，那些场景比卡常还难

左右移运算符优先级低。使用时请注意括号。

二类型转换

定义补码为表示 $T$ , 无符号数表示为 $U$ , 二进制数为 $B$ , 而2则代表to 定义函数 $U 2 B_{w}$ 为无符号数到二进制数转换函数，两者都是 $w$ 位表示的，其他 $U 2 T_{w}$ $T 2 B_{w}$ 以此类推

关于这个的理解：虽然说叫转换，但实际上可以理解为把...当成...看计算出的结果 比如B2T就是把二进制看成补码，得出的结果的十进制表示 这里的B代表的二进制是最基础的01位向量

2.1 无符号数（B2U）

对于向量 $x = [x_{w - 1}, x_{w - 2}, \dots, x_{0}]$ ：

$\begin{matrix} (1) & B 2 U_{w} (x) = \sum_{i = 0}^{w - 1} x_{i} 2^{i} \end{matrix}$

这个和 OI 一些比赛初赛的二进制相关是一样的，可以手动模拟一下，没学过求和符号的可以看这个

$\begin{matrix} (2) & U 2 B_{4} ([1011]) = 1 \times 2^{3} + 0 \times 2^{2} + 1 \times 2^{1} + 1 \times 2^{0} = 11 \end{matrix}$

考虑 $w$ 位二进制表示的最大值和最小值。最小值当然就是0（负数的表示以后会说）最大值即为 $\sum_{i = 0}^{w - 1} 2^{i}$ ，即向量每一位都是1。根据等比数列公式易得 $\sum_{i = 0}^{w - 1} 2^{i} = 2^{w} - 1$

函数 $B 2 U_{w}$ 是一个双射，即任意一个 $[0, 2^{w} - 1]$ 的无符号数都有唯一的二进制表示，同时每个 $w$ 二进制表示都对应唯一一个 $[0, 2^{w} - 1]$ 的无符号数

2.2 补码表示（B2T）

根据补码的定义，易得以下公式（其实手动带个数进去就好了）

$\begin{matrix} (3) & B 2 T_{w} (x) = - x_{w - 1} 2^{w - 1} + \sum_{i = 0}^{w - 2} x_{i} 2^{i} \end{matrix}$

最高为 $x_{w - 1}$ 称为符号位。如果是 $0$ 则 $- 0 = 0$ 所以不计（正数），如果是 $1$ 则 $- 1 = 1$ 乘上 $2^{w - 1}$ 即表示负数如果不知道这种方式为什么能表达补码那么请看下面

首先我们知道补码的定义是反码加一，反码也就是最高位符号位剩下的位都取反。所以

$\begin{matrix} (4) & [1011]_{2 补码} = [1010]_{2 反码} = - [101]_{2} = - (1 \times 2^{2} + 0 + 1 \times 2^{0} = - (4 + 1) = - 5) \end{matrix}$

而根据上面公式

$\begin{matrix} (5) & B 2 T_{4} ([1011]) = - 1 \times 2^{3} + \sum_{i = 0}^{2} x_{i} 2^{i} = - 8 + 1 \times 2^{0} + 1 \times 2^{1} + 0 = - 8 + 1 + 2 = - 5 \end{matrix}$

看明白逻辑了吗？ $B 2 T$ 的公式实际上就是以负的为基准然后加上正的（相当于取反再取反）而常规（按照定义算）是直接取反后加好正的然后取相反数 ~~有些大佬也可以证明一下这两个公式等价~~

和上面一样的推理， $T M a x_{w} = 2^{w - 1} - 1$ ，而 $T M i n_{w} = - 2^{w - 1}$ 有没有感觉熟悉？ $[- 2147483648, 2147483647]$ （即 $- 2^{31}$ 和 $2^{31} - 1$

同样， $B 2 T$ 也是一个双射。

C标准并没有说有符号整数一定要用补码表示，即使大多数实现都是这样做。 Java要求采用补码表示。同时单字节数据是byte而不是char。

2.3 其他表示

我们知道除了补码还有原码和反码。

反码与补码唯一的差别就是一个 $1$ 。所以只要把 $B 2 T$ 公式的最高符号位改为 $- x_{w - 1} (2^{w - 1} - 1)$ 用 $O$ 表示反码 (Ones’ Complement)，则

$\begin{matrix} (6) & B 2 O_{w} (x) = - x_{w - 1} (2^{w - 1} - 1) + \sum_{i = 0}^{w - 2} x_{i} 2^{i} \end{matrix}$

原码的公式也可以很简单地推导出来，这里不再赘述。

这两种表示方法的缺点是 $0$ 可以有两种表示。而且不具备补码在计算上的优势。

待更，还有补码相关内容

写在后面的话：

从发暂退役帖以来已经很久了感谢大家的关心说真的没想到有那么多人评论

我发现我不知道我学习OI的目标是什么，即使我在写题学算法的过程中感受到了快乐

但每次做不出题都会有极大挫败感然后心里那种别扭的劲就总想让逼我更加油一点

而这样慢慢就变成「自己给自己下任务」了，那份纯粹的快乐也没有了

然后越来越焦虑，总觉得自己努力还不够结果陷入恶性循环

Manjaro KDE是真的离谱，设置上外观全没，动不动显卡驱动挂了

有时候调整音量那个显示在屏幕中间的音量大小图标（仿macOS的主题）就会直接截取那个位置上显示的东西然后还自己消失不掉而且这个状态下放任何东西都没声，b站还是别的视频都打不开

点任务栏浏览器也没反应，我

嗯，然后过了好久才反映，这反射弧是NM离谱

CSAPP Today 2021-01-18

一 左移和右移