CSAPP 01 - Bits, Bytes and Integers

Notes for Bits, Bytes and Integers.

宽为 $w$ 的bit向量可用于表示 $A=\{0,\cdots,w-1\}$ 的子集，$j \in A$ 当且仅当 $a_j=1$。

例如，01101001可表示 $\{0, 3, 5, 6\}$；01010101可表示 $\{0, 2, 4, 6\}$。

&，｜，~可分别求集合的交、并、补集。

注： C++提供了bitset库用于管理一系列的bit位。

$-x_{w-1}\cdot2^{w-1}+\sum_{i=0}^{w-2}x_i\cdot2^i$

其中 $w$ 是位宽，最高位第$w-1$是符号位。

int和unsigned相互转换

保留bit模式，但根据符号位的不同含义重新翻译其值。

int和unsigned出现在同一个表达式时，int会被隐式转换成unsigned，从而可能导致一些混乱。

例如：

-1 < 0

-1 > 0U
一段危险的代码
1
2
3
unsigned i;
for (i = cnt - 2; i >= 0; i--)
a[i] = a[i + 1];
unsigned始终不小于0。当其等于0时，再进行一次自减将变成UINT_MAX，从而导致死循环。

sizeof默认返回unsigned，在使用其返回值时同样应注意以上代码的问题。

若想要使用unsigned作为循环索引，正确的姿势是：
1
2
3
unsigned i;
for (i = cnt - 2; i < cnt; i--)
a[i] = a[i + 1];
有符号数的位扩展与截断
位扩展

用现有最高位填充所有扩展位。如short ➡️ int时会发生。
位截断

直接截去多余的位，可能出现正数变负数，负数变正数。如int ➡️ short时会发生。

左移
- $u << k = u * 2^k$
- 对于有符号数和无符号数都适用
右移
- 无符号数采用逻辑移位，有 $u >> k = \lfloor u / 2^k \rfloor$
- 有符号数采用算术移位，有 $u >> k = \lceil u / 2^k \rceil$
- 无符号数的右移等价于除以对应2的幂，有符号数不等价（会向错误的方向进位）