BigInteger的原理是什么？

`BigInteger` 是 Java 中用于**处理大整数**（超过 `long` 最大值 `2^63-1`）的类，它的底层采用 **“数组存储+大数运算”** 来实现 **任意精度整数运算**。 ## **1. `BigInteger` 的核心数据结构** `BigInteger` 的核心是 **用 `int[]` 数组存储大整数**，并配合 `signum` 记录符号。 ```java // BigInteger 核心字段 private final int[] mag; // 存储绝对值的整数数组（big-endian） private final int signum; // 记录符号（-1 表示负数，0 表示零，1 表示正数） ``` ### **🔹 `mag` 数组存储数值** - `mag` 采用 **大端序**（Big-Endian），即**高位在前，低位在后**。 - 每个 `int` 作为 **32 位** 的存储单元，从高位到低位拼接形成完整的数值。 ### **🔹 `signum` 记录正负** - `1`：正数 - `0`：零 - `-1`：负数（`mag` 仍存绝对值，符号由 `signum` 控制） ### **示例：存储 12345678901234567890** ```java BigInteger big = new BigInteger("12345678901234567890"); ``` 其 `mag[]` 存储： ``` mag = {28744523, 232830643} ``` 即： ``` 28744523 × 2^32 + 232830643 ``` （内部用 `int` 作为 32 位块进行拼接） ## **2. `BigInteger` 的基本运算** 由于 `BigInteger` 不依赖固定精度的数据类型，因此**所有运算都是基于数组实现的**，常见运算包括： ### **🔹 加法 (`add()`)** 模拟 **大整数加法**，采用**手动进位**的方式： 1. 对齐 `mag[]` 长度，短的前面补 `0`。 2. 从最低位（数组最后一位）开始相加。 3. 如果相加后大于 `2^32`，则进位。 示例： ```java BigInteger a = new BigInteger("999999999"); BigInteger b = new BigInteger("1"); BigInteger c = a.add(b); System.out.println(c); // 1000000000 ``` 底层步骤： ``` 999999999 (3E8 968F) + 1 (0000 0001) ------------------- 1000000000 (3E8 9690) // 进位 ``` ### **🔹 乘法 (`multiply()`)** 采用 **“小学乘法”+Karatsuba优化**： 1. **小数直接用暴力乘法**（每一位相乘+进位）。 2. **大数使用 Karatsuba 算法**（O(n^log2(3))）。 3. **结果用 `int[]` 存储，并去掉前导 0**。 示例： ```java BigInteger a = new BigInteger("100000"); BigInteger b = new BigInteger("100000"); BigInteger c = a.multiply(b); System.out.println(c); // 10000000000 ``` 底层步骤： ``` 100000 × 100000 ------------------- 10000000000 ``` ### **🔹 除法 (`divide()`)** 使用 **“手写长除法”**： 1. 计算被除数的前几位是否大于除数。 2. 逐步尝试减法，直到得到商。 3. 余数继续计算，直到 `mag[]` 无法再除。 示例： ```java BigInteger a = new BigInteger("1000000000"); BigInteger b = new BigInteger("10000"); BigInteger c = a.divide(b); System.out.println(c); // 100000 ``` 底层步骤： ``` 1000000000 ÷ 10000 = 100000 ``` ### **🔹 取模 (`mod()`)** `mod()` 用于计算 **a % b**，本质上就是 `divide()` 取余： ```java BigInteger a = new BigInteger("1000000000"); BigInteger b = new BigInteger("300000"); BigInteger c = a.mod(b); System.out.println(c); // 100000 ``` ### **🔹 取幂 (`pow()`)** 基于**快速幂算法**： ```java BigInteger a = new BigInteger("2"); BigInteger c = a.pow(10); System.out.println(c); // 1024 ``` 底层使用： ``` pow(10) = (2^2)^5 = (4^2)^2 × 4 ``` **时间复杂度**：O(log n)。 ## **3. `BigInteger` 的优化** 由于 `BigInteger` 需要处理**超大整数**，为了提升性能，采用了以下优化： ### **🔹 Karatsuba 乘法** - 当 `n` 变大时，传统 O(n²) 乘法变慢。 - `BigInteger` 在 `n > 63` 时**自动切换 Karatsuba 算法**，降低时间复杂度到 **O(n^1.58)**。 ### **🔹 费马小定理计算 `modInverse()`** - `BigInteger` 使用 **费马小定理** 快速求模逆： ``` a^(-1) ≡ a^(p-2) (mod p) ``` - 比单纯的扩展欧几里得算法更高效。 ### **🔹 Montgomery 乘法** - **优化模运算**，避免多次除法，提升 `modPow()` 速度。 ## **4. `BigInteger` 与 `long` 的对比** | 比较项 | `BigInteger` | `long` | |--------|------------|-------| | 最大值 | **无限制** | `2^63-1` | | 运算方式 | **数组+大数算法** | **CPU指令** | | 性能 | **较慢**（O(n)) | **极快**（O(1)） | | 内存占用 | **较高** | **低** | ### **什么时候用 `BigInteger`？** - 需要存储超过 `long` 范围的大整数。 - 计算高精度的加、减、乘、除。 - 需要大数运算，如 RSA 加密、密码学计算。 ## **5. 总结** ✅ **`BigInteger` 本质上是“用 `int[]` 实现的无限大整数”** ✅ **加减法用手动进位，乘法用 Karatsuba，除法用长除法** ✅ **采用 `modPow()`、Montgomery 乘法等优化** ✅ **适用于大整数计算，但比 `long` 慢** **结论：`BigInteger` 适用于需要高精度的计算，但性能远不如基本数据类型！**