第一 数字

计算机正如其名，从诞生之日，就是为了进行快速地数值计算，主要用于炮弹的弹道计算。为了搞清楚计算机的工作原理，我们首先要了解数字（尤其是整数）在计算机中是怎么表示的。本章将从最基础的二进制编码出发，逐步深入进制转换、大数运算、浮点数表示、特殊数以及素数与数论等领域，并结合 Rust 代码进行实践。

1.1 编码方式

1.1.1 二进制与编码概述

我们知道计算机中数据都是以 0、1 组成的二进制进行编码、计算、存储、传输的。二进制编码又分为：原码、反码、补码几种编码方式。

• 原码
• 反码
• 补码
• 掩码

所谓原码就是二进制定点表示法，即最高位为符号位，“0“表示正，“1“表示负，其余位表示数值的大小。

1.1.2 原码、反码、补码

原码（Sign-Magnitude）：最高位表示符号，其余位表示数值的绝对值。对于 $n$ 位有符号整数，原码的表示范围为 $[-(2^{n-1}-1), 2^{n-1}-1]$。

$$[x]_{原} = \begin{cases} x & x \geq 0 \ 2^{n-1} + |x| & x < 0 \end{cases}$$

反码（Ones’ Complement）：正数的反码与其原码相同；负数的反码是对正数逐位取反，符号位保持为 1。

$$[x]_{反} = \begin{cases} x & x \geq 0 \ 2^n - 1 + x & x < 0 \end{cases}$$

补码（Two’s Complement）：正数的补码与其原码相同；负数的补码是在其反码的末位加 1。在计算机系统中，数值一律用补码来表示和存储。

$$[x]_{补} = \begin{cases} x & x \geq 0 \ 2^n + x & x < 0 \end{cases}$$

使用补码的好处在于：可以将符号位和数值域统一处理；同时，加法和减法也可以统一处理（减法转化为加负数的补码）。

1.1.3 编码转换规则

原码 => 反码 => 补码

原码 => 补码

(1) 正整数的补码是其二进制表示，与原码相同。

(2) 求负整数的补码，将其原码除符号位外的所有位取反（0 变 1，1 变 0，符号位为 1 不变）后加 1。

补码 => 原码

(1) 如果补码的符号位为“0“，表示是一个正数，其原码就是补码。

(2) 如果补码的符号位为“1“，表示是一个负数，那么求给定的这个补码的补码就是要求的原码。

简而言之：正整数的原码、反码、补码相同；负整数的补码就是在原码的基础上符号位不变，其他位取反（得到反码），然后加 1。

以 -1 为例（假设类型为 i8），-1 的原码为 10000001，反码为 11111110，补码为 11111111。由此可见反码作为原码和补码相互转换的中间码。

1.1.4 编码方式对比表

1.1.5 Rust 整数类型与进制输出

Rust 提供了丰富的整数类型，下面是各类型的取值范围：

#![allow(unused)]
fn main() {
// 十进制
println!("{}", i8::MIN);
println!("{}", i8::MAX);
println!("{}", i16::MIN);
println!("{}", i16::MAX);
println!("{}", i32::MIN);
println!("{}", i32::MAX);
println!("{}", i64::MIN);
println!("{}", i64::MAX);
println!("{}", u8::MIN);
println!("{}", u8::MAX);
println!("{}", u16::MIN);
println!("{}", u16::MAX);
println!("{}", u32::MIN);
println!("{}", u32::MAX);
println!("{}", u64::MIN);
println!("{}", u64::MAX);
}

Rust 支持多种进制的格式化输出：

#![allow(unused)]
fn main() {
// 二进制 10001
println!("0b{:08b}", 17i8);
// 八进制 21
println!("0o{:08o}", 17i8);
// 十六进制 11
println!("0x{:08x}", 17i8);

println!("0b{:08b}", 0i8);
println!("0b{:08b}", 1i8);
println!("0b{:08b}", -1i8);
println!("0b{:08b}", i8::MAX);

println!("0b{:08b}", -2i8);
println!("0b{:08b}", 17u8);
println!("0o{:08o}", 17u8);
println!("0x{:08x}", 17u8);
}

1.2 进制转换

1.2.1 进制转换概述

进制是计数系统的基础。日常生活中我们使用十进制（基数为 10），而计算机使用二进制（基数为 2）。此外，八进制和十六进制也因便于表示二进制而被广泛使用。不同进制之间的转换是程序员的基本功。

进制转换的核心公式：一个 $b$ 进制数 $(d_n d_{n-1} … d_1 d_0)_b$ 转换为十进制：

$$N = d_n \times b^n + d_{n-1} \times b^{n-1} + … + d_1 \times b^1 + d_0 \times b^0 = \sum_{i=0}^{n} d_i \times b^i$$

1.2.2 Excel 表格列名转换（26 进制）

Excel 表格的列名采用了一种特殊的 26 进制表示：A=1, B=2, …, Z=26, AA=27, AB=28, …。这与普通的 26 进制略有不同，因为没有表示 0 的“数字“。

Go 语言实现：

// ColumnNameToNumber provides a function to convert Excel sheet column name
// (case-insensitive) to int. The function returns an error if column name
// incorrect.
//
// Example:
//
//	excelize.ColumnNameToNumber("AK") // returns 37, nil
func ColumnNameToNumber(name string) (int, error) {
	if len(name) == 0 {
		return -1, newInvalidColumnNameError(name)
	}
	col := 0
	multi := 1
	for i := len(name) - 1; i >= 0; i-- {
		r := name[i]
		if r >= 'A' && r <= 'Z' {
			col += int(r-'A'+1) * multi
		} else if r >= 'a' && r <= 'z' {
			col += int(r-'a'+1) * multi
		} else {
			return -1, newInvalidColumnNameError(name)
		}
		multi *= 26
	}
	if col > MaxColumns {
		return -1, ErrColumnNumber
	}
	return col, nil
}

// ColumnNumberToName provides a function to convert the integer to Excel
// sheet column title.
//
// Example:
//
//	excelize.ColumnNumberToName(37) // returns "AK", nil
func ColumnNumberToName(num int) (string, error) {
	if num < MinColumns || num > MaxColumns {
		return "", ErrColumnNumber
	}
	var col string
	for num > 0 {
		col = string(rune((num-1)%26+65)) + col
		num = (num - 1) / 26
	}
	return col, nil
}

Rust 语言实现：

#![allow(unused)]
fn main() {
const MIN_COLUMNS: usize = 1;
const MAX_COLUMNS: usize = 16384;
/// The column number convert to column name
fn column_number_to_name(num: usize) -> std::string::String {
    if num < MIN_COLUMNS || num > MAX_COLUMNS {
        return "".to_string();
    }
    let mut ret = num;
    let mut col = std::string::String::new();
    while ret > 0 {
        let ch = ((ret - 1) % 26 + 65) as u8;
        ret = (ret - 1) / 26;
        col.insert(0, ch as char);
    }

    col
}

///
/// column name convert to column number
fn column_name_to_number(name: std::string::String) -> usize {
    let len = name.len();
    if len == 0 {
        return 0;
    }
    let mut col = 0;
    let bytes = name.as_bytes();
    let mut i = len - 1;
    let mut multi = 1;
    loop {
        let ch = bytes[i];
        if ch >= b'A' && ch <= b'Z' {
            col += multi * (ch - b'A' + 1) as usize;
        } else if ch >= b'a' && ch <= b'z' {
            col += multi * (ch - b'a' + 1) as usize;
        } else {
            return 0;
        }

        if i < 1 {
            break;
        }
        i -= 1;
        multi *= 26;
    }
    if col > MAX_COLUMNS {
        return 0;
    }

    col
}

println!("{}", column_number_to_name(28));
println!("{}", column_name_to_number("AF".to_string()));
}

1.3 实战应用

1.3.1 力扣实战：十进制整数的反码

1009. 十进制整数的反码

原码通过与掩码进行异或（XOR）运算得到“反码“，注意：这里的“反码“和真正的反码定义是不一样的。

pub fn bitwise_complement(n: i32) -> i32 {
    if n == 0 {
        return 1;
    }
    let mut num = n;
    let mut mark = 1;
    let mut high_bit = 0;
    while num > 0 {
        num >>= 1;
        high_bit += 1;
    }

    //dbg!(high_bit);
    let mark = match (high_bit == 31) {
        true => i32::MAX - 1,
        false => (1 << high_bit) - 1,
    };

    n ^ mark
}

fn main() {
    let n = 911;
    let complement = bitwise_complement(n);
    println!("{:032b}", n);
    println!("{:032b}", complement);
}

1.4 大数运算

1.4.1 大整型概述

数值多大才能称得上天文数字呢？天文数字又有何用呢？在现代密码学、科学计算和数论研究中，大数运算是不可或缺的。Rust 的标准整数类型有固定的位数限制，对于超出范围的计算，需要使用专门的大数库。

1.4.2 古戈尔

1 古戈尔 = $10^{100}$（10 的 100 次方）

目前人类发现的最大素数，是 $2^{136279841} - 1$，这个数字有 41,024,320 位。

葛立恒数 葛立恒数诞生于组合数学领域的拉姆齐理论（Ramsey Theory）。这个理论的核心思想是：在足够大的系统中，完全的无序是不可能的，一定会出现某种有规则的子结构

TREE(3) 如果把葛立恒数比作一个原子的大小，那么 TREE(3) 的大小可能相当于一个已知宇宙的规模。在数学上，TREE(3) 的增长速度已经超越了使用葛立恒数定义过程中所使用的递归方法所能达到的极限。更具体地说，TREE(3) 的增长速度远非葛立恒数可比，它已经触及了 “增长速度超越皮亚诺算术” 的领域。

1.4.3 阶乘与末尾零

问题：100 的阶乘（100!）末尾有多少个零呢？

要计算 $n!$（$n$ 的阶乘）末尾有多少个零，其实就是看这个乘积里因子 10 有多少个。而 $10 = 2 \times 5$，在阶乘中因子 2 的数量远多于因子 5，所以末尾零的个数等于因子 5 的个数。

计算方法（勒让德公式）：

$$Z(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{5^k} \right\rfloor = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \cdots$$

以 $n = 100$ 为例：

$$Z(100!) = \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{25} \right\rfloor + \left\lfloor \frac{100}{125} \right\rfloor + \cdots = 20 + 4 + 0 + \cdots = 24$$

答案：100! 的末尾有 24 个零。

1.4.4 Rust 大数运算示例

#![allow(unused)]
fn main() {
use num::bigint::{BigInt, ToBigInt};
/// 计算 x 的阶乘，即 x!
fn factorial(x: i32) -> BigInt {
    if let Some(mut facatorial) = 1.to_bigint() {
        for i in 1..(x + 1) {
            facatorial *= i;
        }
        facatorial
    } else {
        panic!("Failed to calculate factorial!");
    }
}
let result = factorial(100);
println!("{}", result);

use num::BigUint;
let x = BigUint::parse_bytes(b"786fe10f87d8ddfeeeea9a4a49e63388e3b2a9e1b0a794907908f6123dbf6c6a", 16).unwrap();
println!("{}", x);
// SM2 密码算法曲线所使用的质数
let p = BigUint::parse_bytes(b"FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF", 16).unwrap();
println!("{}", p);
}

1.5 浮点数

1.5.1 IEEE 754 标准

现代计算机普遍采用 IEEE 754 标准存储浮点数，主要由三部分组成：

$$\text{浮点数} = (-1)^{sign} \times (1 + mantissa) \times 2^{(exponent - bias)}$$

• 符号位（Sign Bit）：表示浮点数的正负，1 位。
• 指数位（Exponent）：表示浮点数的指数部分，单精度 8 位，双精度 11 位。
• 尾数位（Mantissa/Significand）：表示浮点数的小数部分，单精度 23 位，双精度 52 位。
• 偏置（Bias）：指数部分的偏移量，用于表示负数指数。单精度 bias = 127，双精度 bias = 1023。

1.5.2 浮点数的精度问题

fn main() {
    // 默认是 f64
    let a: f64 = 0.1;
    let b: f64 = 0.2;

    // 使用 f32 精度更低
    let c: f32 = 0.1;
    let d: f32 = 0.2;

    println!("f64: {}", a + b);  // 0.30000000000000004
    println!("f32: {}", c + d);  // 0.3

    // 比较浮点数（不推荐直接使用 ==）
    let x: f64 = 0.1 + 0.2;
    let y: f64 = 0.3;
    println!("直接比较: {}", x == y);  // false

    // 使用容差比较
    let eps = 1e-10;
    println!("容差比较: {}", (x - y).abs() < eps);  // true
}

浮点数的精度问题原因：

• 原因 1：二进制无法精确表示某些十进制小数（如 0.1）
• 原因 2：运算顺序影响精度
• 原因 3：舍入误差累积

解决精度问题

• 方案一：rust_decimal — 高性能金融计算首选
• 方案二：bigdecimal — 任意精度的“瑞士军刀”

1.6 特殊数

1.6.1 数的分类概述

数可以按照多种方式进行分类：整数（奇数、偶数）、浮点数、复数、质数、合数、完美数等。本节介绍两种有趣的特殊数——勾股数和的士数。

1.6.2 勾股数

勾股数（Pythagorean triple）是指满足勾股定理的三个正整数 $(a, b, c)$ 的一组解：

$$a^2 + b^2 = c^2$$

例子：

$$3^2 + 4^2 = 5^2$$ $$5^2 + 12^2 = 13^2$$ $$6^2 + 8^2 = 10^2$$ $$8^2 + 15^2 = 17^2$$ $$7^2 + 24^2 = 25^2$$

勾股数有无穷多组，可以通过欧几里得公式生成：对于任意正整数 $m > n$，令

$$a = m^2 - n^2, \quad b = 2mn, \quad c = m^2 + n^2$$

则 $(a, b, c)$ 必为一组勾股数。

1.6.3 的士数

的士数（Taxicab Number，记为 $Ta(n)$）：能写成 $n$ 组两个正整数立方和的最小正整数。

$$N = a_1^3 + b_1^3 = a_2^3 + b_2^3 = … = a_n^3 + b_n^3$$

最著名的的士数是 $1729 = 1^3 + 12^3 = 10^3 + 9^3$。这个数因数学家哈代和拉马努金的一段著名对话而得名。

1.7 素数与数论

1.7.1 素数概述

质数（素数）是数论的核心研究对象。素数在密码学（如 RSA 算法）、哈希函数、随机数生成等领域有着广泛应用。

素数的主要类型包括：

• 孪生素数：相差为 2 的一对素数，如 (3, 5), (11, 13), (17, 19)
• 梅森素数：形如 $2^p - 1$ 的素数，其中 $p$ 本身也是素数
• 费马素数：形如 $2^{2^n} + 1$ 的素数

1.7.2 素数的定义与性质

定义：质数（prime number）又称素数，有无限个。质数定义为在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数称为质数。

质数的性质：

• 无穷性：质数有无穷多个（欧几里得证明）。
• 分布规律：随着数字增大，质数会变得越来越稀疏。质数定理描述了这种分布：小于 $n$ 的质数个数约为 $\frac{n}{\ln n}$。
• 唯一分解定理（算术基本定理）：任何一个大于 1 的整数，无论它有多大，都可以被唯一地分解成一组质数的乘积。

$$n = p_1^{a_1} \times p_2^{a_2} \times … \times p_k^{a_k}$$

• 素性检验：判断一个大数是否为质数在计算上非常困难，没有简单的通用公式，这也是许多密码系统安全性的基础。

1.7.3 著名猜想与定理

• 费马小定理：对于质数 $p$ 和任意整数 $a$，有 $a^{p-1} \equiv 1 \pmod{p}$。

• 欧拉定理：对于互质的正整数 $a$ 和 $n$，有 $a^{\varphi(n)} \equiv 1 \pmod{n}$，其中 $\varphi(n)$ 是欧拉函数，表示小于 $n$ 且与 $n$ 互质的正整数的个数。

• 哥德巴赫猜想：任何一个大于 2 的偶数，都可以写成两个质数之和。例如，$4 = 2 + 2$，$10 = 3 + 7$。这个猜想至今未被证明，但已被计算机验证到非常大的数。

• 孪生素数猜想：存在无穷多对相差为 2 的质数。目前，数学家张益唐在该问题上取得了里程碑式的突破。

• 黎曼猜想：这是关于质数分布规律的终极猜想，被认为是数学界最重要的未解难题之一。它试图用黎曼 $\zeta$ 函数来精确描述质数的分布：

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \cdots$$

• 克拉茨猜想：对于任意正整数，如果是偶数则除以 2，如果是奇数则乘 3 加 1，重复此过程，最终都会到达 1。

1.8 总结

本章知识点汇总

Rust 整数类型范围

1.9 练习题

1. 基础题：写出 -5（i8 类型）的原码、反码和补码，并用 Rust 代码验证 println!("0b{:08b}", -5i8) 的输出。

2. 进制转换：编写一个 Rust 函数，将十进制整数转换为任意进制（2-36）的字符串表示。

3. Excel 列名：使用 Rust 实现 column_number_to_name 和 column_name_to_number 函数，并编写测试用例验证 1->A, 26->Z, 27->AA, 702->ZZ, 703->AAA 等边界情况。

4. 阶乘末尾零：编写一个 Rust 函数，输入整数 $n$，计算 $n!$ 末尾零的个数。验证 $n = 100$ 时结果为 24，$n = 1000$ 时结果为 249。

5. 浮点数比较：解释为什么 0.1 + 0.2 != 0.3 在计算机中成立，并编写一个 Rust 函数，使用容差法正确比较两个 f64 浮点数是否相等。

6. 勾股数生成：使用欧几里得公式编写 Rust 代码，生成前 10 组本原勾股数（即 $gcd(a, b, c) = 1$ 的勾股数）。

7. 素数判定：编写一个 Rust 函数，使用试除法判断一个正整数是否为素数，并分析其时间复杂度。尝试优化到只需检查到 $\sqrt{n}$。

8. 思考题：在密码学中，为什么需要使用大素数（数百位甚至上千位）？如果素数很小会有什么安全隐患？