Bits, Bytes, and Integers cont¶

1. 无符号加法（Unsigned Addition）¶

• 不能无限制地增加，丢弃进位（discard carry）
  • 原因：计算机的内存是有限的，每个数只能占用固定的位数（比如 32 位或 64 位）。当两个数相加的结果超过了这个位数能表示的范围，超出的部分（进位）就会被丢弃。
  • 公式：
    \( u + v \mod 2^w \)
    其中，\( w \) 是位宽（比如 32 位或 64 位）。这个公式的意思是，加法结果只保留 \( w \) 位，超出的部分会被丢弃。
  • 溢出（Overflow）：当两个无符号数相加的结果超过了 \( 2^w - 1 \) 时，就会发生溢出。比如，8 位无符号数的最大值是 255，如果两个数相加超过了 255，结果就会溢出。

说人话：无符号加法就像你在一个只能显示 3 位数字的计算器上做加法。如果你加 999 + 1，计算器会显示 000，而不是 1000，因为最高位的 1 被丢弃了。

2. 补码加法（Two's Complement Addition）¶

• 补码的特点
  • 补码是一种表示有符号数的方式，它既能表示正数，也能表示负数。负数的补码是通过“取反加 1”得到的。
    比如，-5 的补码是 5 的二进制取反再加 1。
  • 负溢出（Negative Overflow）：当两个负数相加的结果超出了负数能表示的范围时，就会发生负溢出。
    比如，4 位补码能表示的最小负数是 -8，如果你加 -5 + -6 = -11，结果会溢出，变成 5（因为 -11 超出了 4 位补码的范围）。

说人话：补码加法就像你在一个只能显示 4 位数字的计算器上做加法。如果你加 -5 + -6，计算器会显示 5，而不是 -11，因为结果超出了它能表示的范围。

3. 无符号乘法（Unsigned Multiplication in C）¶

• 位宽扩展
  • 无符号数的乘法结果会比原来的数占用更多的位数。比如，两个 32 位的数相乘，结果会占用 64 位。
  • 但计算机通常只保留低位的部分，高位会被丢弃。这相当于对 \( 2^w \) 取模。
  • 溢出时的处理：只保留低 \( w \) 位，高位被丢弃。

说人话：无符号乘法就像你在一个只能显示 4 位数字的计算器上做乘法。如果你乘 1000 * 1000，计算器会显示 0000，而不是 1000000，因为高位被丢弃了。

4. 2 的幂乘法与移位（Power-of-2 Multiply with Shift）¶

• 加权增加
  • 左移操作相当于乘以 \( 2^k \)，其中 \( k \) 是左移的位数。
    比如，左移 1 位相当于乘以 2，左移 2 位相当于乘以 4。
  • 向下取整的原因：左移时，超出位宽的高位会被舍弃，导致结果向下取整。

说人话：左移就像你在一个只能显示 4 位数字的计算器上做乘法。如果你左移 1 位，相当于乘以 2，但如果结果超过了 4 位，高位会被丢弃。

5. 有符号数的乘法（Signed Multiplication）¶

• 移位类型
  • 算术移位（Arithmetic Shift）：保留符号位，适用于有符号数。
  • 逻辑移位（Logical Shift）：不保留符号位，适用于无符号数。
• 偏移处理
  • 在执行除法前，通常需要对数值偏移（Shift），以使结果更接近 0，而不是向下取整。
• 负数取相反数
  • 方法：取反加 1（补码表示法）。

说人话：有符号数的乘法就像你在一个有符号的计算器上做乘法。如果你乘 -5 * 2，计算器会显示 -10，而不是 10，因为它保留了符号位。

6. 溢出（Overflow）¶

• 无符号数的溢出
  • 只有一种溢出：结果超过最大表示范围 \( 2^w - 1 \)。
• 有符号数的溢出
  • 两种溢出：
    1. 正溢出：正数相加结果超出正数范围。
    2. 负溢出：负数相加结果超出负数范围。

说人话：溢出就像你在一个只能显示 4 位数字的计算器上做加法。如果你加 9999 + 1，计算器会显示 0000，而不是 10000，因为结果超出了它能表示的范围。

7. 为什么使用无符号数？¶

• 无符号数（Unsigned）更适合表示计数值、地址等非负数。
• Java 中已经不支持无符号数，但可以通过位运算（例如逻辑右移）间接实现无符号数操作。

说人话：无符号数就像你在数数，永远不会出现负数。比如，数一数你有多少个苹果，这个数永远不会是负数。

8. Java 特殊右移操作¶

• 三重右移运算（Triple Right Shift）
  • 符号：>>>，表示逻辑右移（Logical Shift）。
  • 特点：用 0 填充左侧空位，适用于无符号数。
• 普通右移运算（>>）
  • 符号：>>，表示算术右移（Arithmetic Shift）。
  • 特点：用符号位填充左侧空位，适用于有符号数。

说人话：Java 的右移操作就像你在移动数字的位置。如果你用 >>>，左边会补 0；如果你用 >>，左边会补符号位。

9. 代码片段分析¶

size_t i;
for(i = cnt - 2; i < cnt; i--)
    a[i] += a[i + 1];

• 问题分析：
  • size_t 是无符号类型，i-- 时，当 \( i = 0 \) 后，\( i \) 会溢出变为 \( 2^w - 1 \)。
  • 循环条件 \( i < cnt \) 恒为真，因为 \( i \) 溢出后变成了一个非常大的无符号数，永远大于等于 \( cnt \)。
• 改进建议：
  • 如果需要控制循环条件，避免使用无符号类型，改用有符号类型（如 int）。

说人话：这段代码的问题在于，当 i 变成 0 后，再减 1 会变成一个非常大的数，导致循环永远不会结束。为了避免这个问题，应该用有符号数来控制循环。

10. 总结：计算机存储表示的影响¶

计算机内存的存储和表示方式对编程至关重要。理解这些机制可以帮助我们避免潜在陷阱，提高软件开发效率。

说人话：计算机的内存是有限的，理解它如何存储和处理数据可以帮助你写出更好的代码，避免一些常见的错误。