Java实现大整数乘法：从竖式模拟到进阶优化全解析

## 🛠️ 准备工作 ### 依赖与环境 - **Java 版本**：JDK 8 或更高版本（推荐 JDK 11+） - **开发工具**：IntelliJ IDEA、Eclipse 或 VS Code（需安装 Java 扩展） - **编译运行**： ```bash javac Main.java # 编译 java Main # 运行 ``` - **常见问题**： - 若提示“javac 不是内部命令”，请检查 JDK 是否安装并配置了环境变量。 - Windows 系统建议使用 PowerShell 或 CMD 运行命令。 --- ## 🧮 解题思路 由于题目要求**不能使用高精度库**，且整数可能长达 40 位（远超 `long` 类型的范围），我们需要手动实现**大整数乘法**。这里采用**模拟竖式乘法**的方法： 1. 将两个大整数以字符串形式读入。 2. 反转字符串，方便从低位开始计算。 3. 逐位相乘，处理进位。 4. 最后反转结果字符串，得到正确顺序的乘积。 **关键点**： - 注意处理乘数为 `"0"` 的情况。 - 注意前导零的去除。 - 时间复杂度：O(n*m)，其中 n、m 为两个数字的位数。 --- ## 📝 代码实现 ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String num1 = scanner.nextLine().trim(); String num2 = scanner.nextLine().trim(); scanner.close(); // 处理乘数为0的情况 if ("0".equals(num1) || "0".equals(num2)) { System.out.println("0"); return; } String result = multiply(num1, num2); System.out.println(result); } // 大整数乘法函数 public static String multiply(String num1, String num2) { int len1 = num1.length(); int len2 = num2.length(); int[] result = new int[len1 + len2]; // 结果数组，长度最多为 len1+len2 // 反转字符串，从低位开始计算 StringBuilder sb1 = new StringBuilder(num1).reverse(); StringBuilder sb2 = new StringBuilder(num2).reverse(); // 模拟竖式乘法 for (int i = 0; i < len1; i++) { for (int j = 0; j < len2; j++) { int digit1 = sb1.charAt(i) - '0'; int digit2 = sb2.charAt(j) - '0'; result[i + j] += digit1 * digit2; // 累加到对应位置 } } // 处理进位 for (int i = 0; i < result.length - 1; i++) { if (result[i] >= 10) { result[i + 1] += result[i] / 10; // 进位 result[i] %= 10; // 保留个位 } } // 转换为字符串，并去除前导零 StringBuilder sb = new StringBuilder(); for (int i = result.length - 1; i >= 0; i--) { // 跳过结果数组末尾可能存在的未使用的零 if (sb.length() == 0 && result[i] == 0) { continue; } sb.append(result[i]); } return sb.toString(); } } ``` --- ## 🔍 代码解释 ### 核心函数 `multiply` | 步骤 | 说明 | |------|------| | 1. 初始化结果数组 | `int[] result = new int[len1 + len2]`，长度足够容纳最大可能位数。 | | 2. 反转字符串 | 方便从**个位**开始逐位计算。 | | 3. 双重循环相乘 | 将每一位相乘的结果累加到 `result[i+j]` 位置，模拟竖式乘法的对齐方式。 | | 4. 统一处理进位 | 遍历结果数组，将超过 10 的部分进位到高位。 | | 5. 转换为字符串 | 从高位到低位拼接数字，并跳过前导零。 | ### 示例演示（输入 "111" × "111"） ``` 步骤1: 反转 -> "111", "111" 步骤2: 逐位相乘： 1*1 -> result[0]=1 1*1+1*1 -> result[1]=2 ... 最终 result = [1, 2, 3, 2, 1] 步骤3: 反转 -> "12321" ``` --- ## ⚡ 进阶优化与注意事项 ### 1. 性能优化 - **Karatsuba 算法**：可将时间复杂度降至 O(n^log₂³) ≈ O(n^1.585)，适合极大整数（百位以上）。 - **空间优化**：可使用 `StringBuilder` 直接操作，减少数组转换开销。 ### 2. 错误处理建议 ```java // 输入验证示例 if (num1 == null || num2 == null || num1.isEmpty() || num2.isEmpty()) { throw new IllegalArgumentException("输入不能为空"); } if (!num1.matches("\\d+") || !num2.matches("\\d+")) { throw new IllegalArgumentException("输入必须为十进制正整数"); } ``` ### 3. 常见陷阱 - **前导零处理**：如输入 "00123"，应视为 "123"，否则乘法会出错。 - **大整数负数**：本题未要求，若需支持负数，可先记录符号位，取绝对值计算后补回符号。 - **内存占用**：结果数组长度设为 `len1+len2` 可能略大于实际需要，但保证不会溢出。 --- ## 📚 扩展学习资源 | 主题 | 推荐资源 | |------|----------| | 大整数算法 | 《算法导论》第 30 章（整数运算） | | Java 高精度 | [BigInteger 源码](https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/math/BigInteger.java)（参考官方实现） | | 高效乘法算法 | [Karatsuba 算法详解](https://en.wikipedia.org/wiki/Karatsuba_algorithm) | | 在线练习平台 | [LeetCode 43. 字符串相乘](https://leetcode.com/problems/multiply-strings/) | --- ## 💡 开发建议 1. **代码可读性**：添加详细注释，尤其是算法关键步骤。 2. **单元测试**：编写测试用例覆盖边界情况（如乘数为0、1、40位最大值等）。 3. **模块化设计**：将乘法函数独立为工具类，方便其他项目复用。 4. **性能监控**：对于更大整数（如千位以上），考虑使用更高效的算法。 --- ######[AI写代码神器 | 1541点数解答 | 2026-03-19 17:44:12]