编码夯基

写这一篇的起源，是在做一道简单的leetcode题目：231. 2 的幂 - 力扣（LeetCode）

我使用的是模拟法：

bool isPowerOfTwo(int n) {
    int i = 0;
    int current;
    while(i <= 31){
        current = pow(2,i);
        if(current == n){
            break;
        }
        i++;
    }
    return current == n;
}

然后运行，提示在最后一个测试点n = -2147483648时出错。这就涉及到了编码的知识，然鹅我在大一上学期并没有学好💦

先复习一下几种编码：

Create by Gemini

1. 原码 (Sign-Magnitude)

核心逻辑：最高位为符号位（0 为正，1 为负），其余各位代表数值的绝对值。

特点：最符合人类直觉，左边第一位看正负，后面看大小。
示例：
$+1 \rightarrow [0000 0001]_{\text{原}}$ $-1 \rightarrow [1000 0001]_{\text{原}}$
致命缺陷：
1. 零不唯一：存在 +0 (0000 0000) 和 -0 (1000 0000)。
2. 加减法复杂：计算 1 + (-1) 时，原码运算为 0000 0001 + 1000 0001 = 1000 0010（结果为 -2），硬件需要额外的逻辑来处理符号位。

2. 反码 (Ones’ Complement)

核心逻辑：正数的反码与原码相同；负数的反码是其原码除符号位外，各位取反（0 变 1，1 变 0）。

引入目的：为了尝试解决减法问题。
示例：
$+1 \rightarrow [0000 0001]_{\text{反}}$ $-1 \rightarrow [1111 1110]_{\text{反}}$
缺陷：虽然解决了部分加减逻辑，但零不唯一的问题依然存在（+0 是 0000 0000，-0 是 1111 1111）。

3. 补码 (Two’s Complement) —— 现代计算机的标准

核心逻辑：正数的补码与原码相同；负数的补码是其反码加 1。

工程意义：补码是目前所有主流 CPU（x86, ARM 等）存储整数的方式。
示例：
- -1 的计算过程：
  1. 原码：1000 0001
  2. 反码：1111 1110 (除符号位外取反)
  3. 补码：1111 1111 (反码加 1)
优势：
1. 零唯一：只有 0000 0000 表示 0。
2. 运算统一：减法直接转加法。
  $1 - 1 \rightarrow 1 + (-1) = 0000 0001 + 1111 1111 = 0000 0000 (进位被舍弃)。$
3. 多出一位：原码中浪费的 -0 空间，在补码中被用来表示最小负数（如 8 位的 -128）。

4. 移码 (Excess-K / Offset Binary)

核心逻辑：

在数值上加上一个固定的偏移量（通常是2^{n-1}）。简单来说，就是将补码的符号位取反。

应用场景：主要用于**浮点数（IEEE 754 标准）的阶码（Exponent）**部分。
示例 (8 位)：
- +1 的补码是 0000 0001，移码是 1000 0001。
- 0 的移码是 1000 0000。
意义：移码保持了数据的“单调性”。在移码表示下，全 0 是最小值，全 1 是最大值。这方便 CPU 直接比较两个指数的大小，而不需要考虑复杂的符号位逻辑。

我们可以知道，补码是最重要的编码，这是因为它方便了减法运算。

但是，为什么补码能方便减法运算？🤔这就与数学当中的模运算有关。

首先，在 8 位二进制运算中，模是 2^8 = 256。这意味着：任何减去 X 的操作，都可以用加上 (256 - X) 来代替。

而产生的进位（一定会产生），则会被舍弃，这个效果，也就等价于模256（在这里，也就等同于减去256）。

这里的256 - X，也就是补码。而补码是便于计算的：只要“取反加1”即可。

但是，为什么补码等于反码加一？🤔

因为在二进制中：

取反：X 加上它的反码，结果一定是全 1（例如 0011 + 1100 = 1111）。
在 n 位二进制中，全 1 代表的值是 2^n - 1。
所以：
$\text{反码} = (2^n - 1) - X。$
由此推导：
$\text{反码} + 1 = (2^n - 1) - X + 1 = \mathbf{2^n - X} = \text{补码} 。$

回到题目，n = -2147483648，即n = - 2 ^ 31。

这时我尝试计算 2 ^ 31，然而这个值已经超过了int的范围，产生了有符号整数溢出。

2 ^ 31 - 1 的二进制是 01111111 11111111 11111111 11111111（最高位为符号位）。

-2147483648 即 -2 ^ 31，在内存中以补码形式存储为：10000000 00000000 00000000 00000000。这与我设想的2 ^ 31的值是相同的。所以返回了True，导致测试点错误。