BigInteger 的基本概念

1. 什么是 BigInteger

• BigInteger 是 java.math 包中的类，专门用于表示任意精度的整数。
• 它解决了基本数据类型（如 int、long）的精度限制问题。比如：
  • int 的最大值是 2³¹-1（21 亿）。
  • long 的最大值是 2⁶³-1（约 19 位十进制数）。
  • 如果需要表示更大的整数，就必须使用 BigInteger。

2. 特点

• 不可变性：
  • BigInteger 是不可变对象，每次运算都会返回新的实例，而不会修改原有对象。
• 任意精度：
  • 只受限于可用内存的大小，因此可以表示超大整数。
• 底层实现：
  • BigInteger 底层采用 int[] 数组存储数据，每个数组元素存储一部分数字，并通过数学算法进行操作。
  • 例如，将一个非常大的数字按 32 位一段分开存储。

---

BigInteger 的构造方式

构造函数

BigInteger 提供了多个构造器用于创建实例。

1. 使用字符串构造

这是最常用的构造方法，支持任意大小的数字：

BigInteger bigInt = new BigInteger("123456789012345678901234567890");

• 参数：
  • 字符串表示的数字（支持正负号）。
  • 如果字符串中包含非法字符（如字母），会抛出 NumberFormatException。

2. 使用基本数据类型的转换

通过静态方法 BigInteger.valueOf 将 int 或 long 转换为 BigInteger：

BigInteger bigInt = BigInteger.valueOf(123456789L);

• 注意：
  • valueOf 方法只支持 long 范围内的数值。
  • 对于更大的数字，仍需使用字符串构造。

3. 从二进制、八进制、十六进制等进制构造

支持指定进制的字符串构造：

BigInteger bigInt = new BigInteger("1010", 2); // 二进制 -> 十进制：10
BigInteger hexInt = new BigInteger("1A", 16); // 十六进制 -> 十进制：26

4. 生成随机数

通过构造一个随机数：

BigInteger randomBigInt = new BigInteger(50, new Random()); // 生成 50 位随机数

• 参数含义：
  • 第一个参数是位数（bit 数）。
  • 第二个参数是随机数生成器。

5. 常用常量

BigInteger.ZERO   // 表示 0
BigInteger.ONE    // 表示 1
BigInteger.TEN    // 表示 10

---

BigInteger 的常用操作

1. 算术运算

BigInteger a = new BigInteger("12345");
BigInteger b = new BigInteger("67890");

加法

BigInteger sum = a.add(b); // 结果：80235

减法

BigInteger diff = a.subtract(b); // 结果：-55545

乘法

BigInteger product = a.multiply(b); // 结果：838102050

除法

BigInteger quotient = b.divide(a); // 结果：5

取模

BigInteger mod = b.remainder(a); // 结果：12345

• 注意：divide 是整数除法，不会产生小数部分。

混合运算：加法、乘法

所有的运算都是链式的。例如：

BigInteger result = a.add(b).multiply(a).divide(b);

2. 幂运算

• 普通幂运算（不取模）：

BigInteger base = new BigInteger("2");
BigInteger result = base.pow(10); // 2^10 = 1024

• 模幂运算（大数运算中常用）：

BigInteger base = new BigInteger("2");
BigInteger exp = new BigInteger("10");
BigInteger mod = new BigInteger("7");
BigInteger modPowResult = base.modPow(exp, mod); // (2^10) % 7 = 2

底层优化：

• 模幂运算采用了指数平方算法，时间复杂度为 O(log(n)) ，比逐步计算效率更高。

3. 比较和最大最小值

比较大小

compareTo 方法返回以下结果：

• 1：当前对象大于比较对象。
• -1：当前对象小于比较对象。
• 0：两者相等。
  示例：

int compare = a.compareTo(b);

最大值和最小值

• 返回两个数中的较大或较小值：

BigInteger max = a.max(b);
BigInteger min = a.min(b);

4. 位运算

按位操作

• 按位与：

BigInteger result = a.and(b);

• 按位或：

BigInteger result = a.or(b);

• 按位异或：

BigInteger result = a.xor(b);

位移操作

• 左移：

BigInteger result = a.shiftLeft(2); // 左移 2 位

• 右移：

BigInteger result = a.shiftRight(2); // 右移 2 位

5. 数学相关

求绝对值

BigInteger abs = a.abs();

求最大公约数

BigInteger gcd = a.gcd(b); // 返回 a 和 b 的最大公约数

模反元素

模反元素是满足以下公式的整数：

(a × x) % m = 1

代码示例：

BigInteger modInverse = a.modInverse(mod); // 计算 a 的模反元素

检查是否是质数

boolean isPrime = a.isProbablePrime(10); // 参数为测试的可信度

• 参数是一个整数，值越大，测试结果的可靠性越高。

6. 进制转换

• 转为字符串（默认十进制）：

String decimalStr = a.toString();

• 转为其他进制表示：

String binaryStr = a.toString(2);  // 二进制
String hexStr = a.toString(16);   // 十六进制

---

优化

1. 不可变性

BigInteger 的每次操作都会返回一个新对象。如果需要频繁修改值，可以考虑复用变量以减少对象创建。

2. 注意内存消耗

超大整数会消耗较多内存。例如：

BigInteger big = new BigInteger("9".repeat(1000000)); // 100 万位数字