如何使用任意大的整数而不使用java.math.BigInteger来进行算术运算+ - / * % !？
例如，Java中90的阶乘返回0。我想能够解决这个问题。
如何在Java中处理非常大的数字而不使用java.math.BigInteger？
72
- frodosamoa
12
3为什么你想要替换它？ - Lotfi
28将"How"替换为"Why"就成了一个很好的问题。 - Mark Peters
3"600太小了。寻找大素数的人需要数百万位数字。" - John
1根据你的问题，你可以使用脚本语言或者其他JVM语言。Scala有一个BigInt类型，带有重载运算符。 - josefx
4(int) factorial(34) == 0，(long) factorial(66) == 0，如果您只取一个大数字的最后几位，就不应该期望得到正确的答案。这个问题最近在https://dev59.com/zW435IYBdhLWcg3wmxXz#5317898上有所涉及。 - Peter Lawrey
显示剩余7条评论
7个回答
263
我认为程序员应该实现自己的大数字库，欢迎来到这里。
(当然，后来你会发现BigInteger更好用，会使用它，但它是一次有价值的学习经历。)
（你可以在github上跟踪这个课程的源代码：链接。此外，我重新制作了这个（稍微改进了一下），并将其制作成了一个包含14部分的博客系列：链接。）
在Java中创建一个简单的大数字类
那么，我们需要什么？
首先，需要一种表示数字的方式，
基于Java提供的数据类型。
由于你认为十进制转换是最复杂的部分，让我们保持十进制模式。为了提高效率，我们不会存储真正的十进制数位，而是使用基数1 000 000 000 = 10^9 < 2^30进行工作。这适用于Java的int（最多可达到2^31或2^32），并且两个这样的数位乘积可以很好地适应Java的long。
final static int BASE = 1000000000;
final static int BASE_DECIMAL_DIGITS = 9;
接下来是数字数组：
private int[] digits;
我们把数字存储在小端还是大端，即先放大的部分还是后放？这其实并不重要，所以我们决定采用大端方式，因为这符合人类阅读的习惯。（暂时只集中于非负数值-稍后我们会为负数添加一个符号位。）
为了测试目的，我们添加了一个构造函数，它允许从int[]数组进行初始化。
/**
* creates a DecimalBigInt based on an array of digits.
* @param digits a list of digits, each between 0 (inclusive)
* and {@link BASE} (exclusive).
* @throws IllegalArgumentException if any digit is out of range.
*/
public DecimalBigInt(int... digits) {
for(int digit : digits) {
if(digit < 0 || BASE <= digit) {
throw new IllegalArgumentException("digit " + digit +
" out of range!");
}
}
this.digits = digits.clone();
}
作为额外的奖励，如果一个int小于BASE，那么这个构造函数也可以使用。甚至可以在没有int的情况下使用（我们将其解释为0）。所以现在我们可以这样做：
DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
这使我们得到了
de.fencing_game.paul.examples.DecimalBigInt@6af62373，并不是很有用。所以，我们添加了一个toString()方法：/**
* A simple string view for debugging purposes.
* (Will be replaced later with a real decimal conversion.)
*/
public String toString() {
return "Big" + Arrays.toString(digits);
}
现在的输出是Big[7, 5, 2, 12345]，对于测试而言更加有用，不是吗？
第二步，十进制格式转换。
我们很幸运：我们的基数（10^9）是我们想要转换的基数（10）的幂。因此，我们始终有相同数量（9个）的十进制数字表示一个“我们的格式”数字。（当然，在开始时可能会少一些数字。）在下面的代码中，decimal是一个包含十进制数字的字符串。
int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
这个奇怪的公式是 Java 中写作 bigLen = ceil(decLen/BASE_DECIMAL_DIGITS) 的方式。(我希望它是正确的，我们稍后会测试一下。)
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
这是第一块十进制数字的长度，应该在1到9之间（包括1和9）。
我们创建了我们的数组：
int[] digits = new int[bigLen];
循环遍历要创建的数字:
for(int i = 0; i < bigLen; i++) {
原数中每个数字都由一组数字块表示，其中包含我们的每个数字：
String block =
decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
firstSome + i *BASE_DECIMAL_DIGITS);
(在第一个较短的块中需要使用Math.max。) 我们现在使用通常的整数解析函数，并将结果放入数组中:
digits[i] = Integer.parseInt(block);
}
现在我们从创建的数组中创建DecimalBigInt对象：
return new DecimalBigInt(digits);
让我们看看这是否有效：
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);
输出:
Big[12, 345678901, 234567890]
看起来没问题 :-) 我们还应该用一些不同长度的数字进行测试。
下一步是十进制格式化，这应该更容易。
第三步，转换为十进制格式。
我们需要将每个单独的数字输出为9个十进制数字。为此，我们可以使用Formatter类，它支持类似printf的格式字符串。
一个简单的变体可能是：
public String toDecimalString() {
Formatter f = new Formatter();
for(int digit : digits) {
f.format("%09d", digit);
}
return f.toString();
}
这将返回我们两个数字的
000000007000000005000000002000012345和000000012345678901234567890。这对于往返（即将其提供给valueOf方法会给出一个等效的对象）是有效的，但前导零不太好看（并且可能会与八进制数字产生混淆）。因此，我们需要拆开我们美丽的for-each循环，并为第一个数字和后续数字使用不同的格式化字符串。public String toDecimalString() {
Formatter f = new Formatter();
f.format("%d", digits[0]);
for(int i = 1; i < digits.length; i++) {
f.format("%09d", digits[i]);
}
return f.toString();
}
加法
我们从加法开始，因为这很简单（而且我们之后可以用它的某些部分来进行乘法）。
/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
...
}
我希望方法名称可以像公式一样易于阅读，因此使用
plus,minus,times而不是add,subtract,multiply。那么，加法是如何工作的？ 它与我们在学校中学到的十进制数字大于9的加法相同：添加相应的数字，如果其中某些数字的结果大于10（或者在我们的情况下是
BASE），则向下一个数字进位1。这可能导致结果数字比原始数字多一位。首先，我们观察两个数字具有相同位数的简单情况。然后它看起来就像这样：
int[] result = new int[this.digits.length];
int carry = 0;
for(int i = this.digits.length-1; i > 0; i--) {
int digSum = carry + this.digits[i] + that.digits[i];
result[i] = digSum % BASE;
carry = digSum / BASE;
}
if(carry > 0) {
int[] temp = new int[result.length + 1];
System.arraycopy(result, 0, temp, 1, result.length);
temp[0] = carry;
result = temp;
}
return new DecimalBigInt(result);
（我们从右往左进行，因此我们可以将任何溢出进位到下一位数字。如果我们决定使用Little Endian格式，这将会更美观一些。）
（如果两个数字的位数不相同，则变得有点复杂。）
（为了让它尽可能简单，我们将其拆分为几种方法：）
（该方法向数组中的一个元素添加一个数字（该元素可能已经包含某些非零值），并将结果存回数组。如果发生了溢出，我们通过递归调用将其进位到下一个数字（索引少1而不是多1）。通过这种方式，我们确保我们的数字始终处于有效范围内。）
/**
* adds one digit from the addend to the corresponding digit
* of the result.
* If there is carry, it is recursively added to the next digit
* of the result.
*/
private void addDigit(int[] result, int resultIndex,
int addendDigit)
{
int sum = result[resultIndex] + addendDigit;
result[resultIndex] = sum % BASE;
int carry = sum / BASE;
if(carry > 0) {
addDigit(result, resultIndex - 1, carry);
}
}
下一个函数将为要添加的整个数字数组执行相同的操作：
/**
* adds all the digits from the addend array to the result array.
*/
private void addDigits(int[] result, int resultIndex,
int... addend)
{
int addendIndex = addend.length - 1;
while(addendIndex >= 0) {
addDigit(result, resultIndex,
addend[addendIndex]);
addendIndex--;
resultIndex--;
}
}
现在我们可以实现我们的
plus方法：/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
int[] result = new int[Math.max(this.digits.length,
that.digits.length)+ 1];
addDigits(result, result.length-1, this.digits);
addDigits(result, result.length-1, that.digits);
// cut of leading zero, if any
if(result[0] == 0) {
result = Arrays.copyOfRange(result, 1, result.length);
}
return new DecimalBigInt(result);
}
我们可以在创建数组之前先检查是否存在溢出的可能性，只有在必要时才将数组创建得比需要大一个位置。
啊，还有一个测试：
d2.plus（d2） 返回 Big [24, 691357802, 469135780] ，看起来没问题。
乘法。
让我们回忆一下学校里如何在纸上乘大数？123 * 123
----------
369 <== 123 * 3
246 <== 123 * 2
123 <== 123 * 1
--------
15129
所以，我们需要将第一个数字的每个digit[i]与第二个数字的每个digit[j]相乘，并将结果的digit[i+j]中的乘积相加（并注意进位）。当然，在这里，索引是从右侧开始计算的，而不是从左侧开始。 （现在我真希望我使用了小端数字。）
由于我们的两个数字中的某些digit的乘积可能超出int范围，因此我们使用long进行乘法。
/**
* multiplies two digits and adds the product to the result array
* at the right digit-position.
*/
private void multiplyDigit(int[] result, int resultIndex,
int firstFactor, int secondFactor) {
long prod = (long)firstFactor * (long)secondFactor;
int prodDigit = (int)(prod % BASE);
int carry = (int)(prod / BASE);
addDigits(result, resultIndex, carry, prodDigit);
}
现在我们可以看到为什么我声明了
addDigits方法需要一个resultIndex参数。（我刚刚将最后一个参数更改为变长参数，以便更好地编写此处。）因此，这里是叉乘方法：
private void multiplyDigits(int[] result, int resultIndex,
int[] leftFactor, int[] rightFactor) {
for(int i = 0; i < leftFactor.length; i++) {
for(int j = 0; j < rightFactor.length; j++) {
multiplyDigit(result, resultIndex - (i + j),
leftFactor[leftFactor.length-i-1],
rightFactor[rightFactor.length-j-1]);
}
}
}
希望我计算索引没错。对于小端存储的情况，它将是multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - 很清晰明了，不是吗？
现在我们的times方法只需要分配结果数组，调用multiplyDigits，并封装结果即可。
/**
* returns the product {@code this × that}.
*/
public DecimalBigInt times(DecimalBigInt that) {
int[] result = new int[this.digits.length + that.digits.length];
multiplyDigits(result, result.length-1,
this.digits, that.digits);
// cut off leading zero, if any
if(result[0] == 0) {
result = Arrays.copyOfRange(result, 1, result.length);
}
return new DecimalBigInt(result);
}
为了测试，d2.times(d2) 的结果是 Big[152, 415787532, 388367501, 905199875, 19052100]，这与我的 Emacs calc 计算的结果相同。
比较
我们希望能够比较两个对象。因此，我们实现了 Comparable<DecimalBigInt> 和它的 compareTo 方法。
public int compareTo(DecimalBigInt that) {
怎样判断一个数字是否比另一个数字大？首先，我们要比较数组的长度。由于我们确保不会产生前导零（对吗？），因此更长的数组应该包含更大的数字。
if(this.digits.length < that.digits.length) {
return -1;
}
if (that.digits.length < this.digits.length) {
return 1;
}
如果长度相同，我们可以逐个元素进行比较。由于我们使用大端序（即“大端在前”），因此我们从开头开始。
for(int i = 0; i < this.digits.length; i++) {
if(this.digits[i] < that.digits[i]) {
return -1;
}
if(that.digits[i] < this.digits[i]) {
return 1;
}
}
如果一切都相同，显然我们的数字是相同的，可以返回
0。 return 0;
}
equals + hashCode()
每个良好的不可变类都应该以适当（且兼容）的方式实现equals()和hashCode()。
对于我们的hashCode()，我们只需将数字相加，用小质数乘以它们，以确保数字交换不会导致相同的哈希码：
/**
* calculates a hashCode for this object.
*/
public int hashCode() {
int hash = 0;
for(int digit : digits) {
hash = hash * 13 + digit;
}
return hash;
}
在
equals()方法中，我们可以简单地委托给compareTo方法，而不是再次实现相同的算法：/**
* compares this object with another object for equality.
* A DecimalBigInt is equal to another object only if this other
* object is also a DecimalBigInt and both represent the same
* natural number.
*/
public boolean equals(Object o) {
return o instanceof DecimalBigInt &&
this.compareTo((DecimalBigInt)o) == 0;
}
今天讲解到这里。减法（以及负数）和除法更为复杂，因此暂时省略。对于计算90的阶乘来说，这应该已经足够了。计算大阶乘的方法如下：
计算大阶乘：
下面是阶乘函数：
/**
* calculates the factorial of an int number.
* This uses a simple iterative loop.
*/
public static DecimalBigInt factorial(int n) {
DecimalBigInt fac = new DecimalBigInt(1);
for(int i = 2; i <= n; i++) {
fac = fac.times(new DecimalBigInt(i));
}
return fac;
}
这让我们能够
fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
将任意基数表示法转换
受到frodosamoa的下一个问题的启发，我写了一个回答，说明如何从我们可以（或想要）计算的一种任意（位置）数字系统中进行转换。（在那个例子中，我把三进制转换成十进制，而问题是关于十进制转二进制的。）
在这里，我们希望将一个任意的数字系统（好的，基数介于2和36之间，因此我们可以使用Character.digit()将单个数字转换为整数）转换为以基数BASE（= 1,000,000,000，但这在这里并不重要）为基础的系统。
基本上，我们使用Horner方案，以我们的基数为点，计算多项式系数为数字的值。
sum[i=0..n] digit[i] * radix^i
可以使用以下循环计算：
value = 0;
for i = n .. 0
value = value * radix + digit[i]
return value
由于我们的输入字符串是大端序，因此我们不必倒数计数，而可以使用一个简单的增强型 for 循环。(在 Java 中看起来更丑陋，因为我们没有运算符重载，也没有从 int 自动装箱到我们的 DecimalBigInt 类型。)
public static DecimalBigInt valueOf(String text, int radix) {
DecimalBigInt bigRadix = new DecimalBigInt(radix);
DecimalBigInt value = new DecimalBigInt(); // 0
for(char digit : text.toCharArray()) {
DecimalBigInt bigDigit =
new DecimalBigInt(Character.digit(digit, radix));
value = value.times(bigRadix).plus(bigDigit);
}
return value;
}
在我的实际实现中，我添加了一些错误检查（和异常抛出）以确保我们真的有一个有效的数字，并且当然还有一个文档注释。
将数字转换为任意进制是更加复杂的，因为它涉及到余数和除法（通过任意基数），而我们还没有实现 - 所以暂时不考虑。当我有了一个好的做除法的想法时，就会完成它。（这里我们只需要针对小（一位数）数字进行除法运算，这可能比一般的除法运算更容易。）
小数的除法运算
在学校里，我学过长除法。这里以德国我们通常使用的标记法表示小（一位数）除数的例子，并注明了背景计算（通常我们不写），以十进制为例：
12345 : 6 = 02057 1 / 6 = 0
-0┊┊┊┊ 0 * 6 = 0
──┊┊┊┊
12┊┊┊ 12 / 6 = 2
-12┊┊┊ 2 * 6 = 12
──┊┊┊
03┊┊ 3 / 6 = 0
- 0┊┊ 0 * 6 = 0
──┊┊
34┊ 34 / 6 = 5
-30┊ 5 * 6 = 30
──┊
45 45 / 6 = 7
-42 7 * 6 = 42
──
3 ==> quotient 2057, remainder 3.
当然，如果我们有原生的余数运算，我们就不需要计算这些乘积（0、12、0、30、42）并从中减去。那么它看起来像这样（当然，在这里我们不需要编写操作）：
12345 : 6 = 02057 1 / 6 = 0, 1 % 6 = 1
12┊┊┊ 12 / 6 = 2, 12 % 6 = 0
03┊┊ 3 / 6 = 0, 3 % 6 = 3
34┊ 34 / 6 = 5, 34 % 6 = 4
45 45 / 6 = 7, 45 % 6 = 3
3
==> quotient 2057, remainder 3.
如果我们用另一种格式书写，这看起来已经非常像短除法。
我们可以观察（并证明）以下内容：
如果我们有一个两位数x，其第一位小于除数d，那么x / d是一个一位数，而x％d也是一个一位数，小于d。 这个结论连同归纳法表明，我们只需要用除数去除（余数）两位数。
回到我们的基数为BASE的大数字：所有的两位数都可以表示为Java中的long，而且我们还有本地的/和%操作符。
/**
* does one step in the short division algorithm, i.e. divides
* a two-digit number by a one-digit one.
*
* @param result the array to put the quotient digit in.
* @param resultIndex the index in the result array where
* the quotient digit should be put.
* @param divident the last digit of the divident.
* @param lastRemainder the first digit of the divident (being the
* remainder of the operation one digit to the left).
* This must be < divisor.
* @param divisor the divisor.
* @returns the remainder of the division operation.
*/
private int divideDigit(int[] result, int resultIndex,
int divident, int lastRemainder,
int divisor) {
assert divisor < BASE;
assert lastRemainder < divisor;
long ent = divident + (long)BASE * lastRemainder;
long quot = ent / divisor;
long rem = ent % divisor;
assert quot < BASE;
assert rem < divisor;
result[resultIndex] = (int)quot;
return (int)rem;
}
我们现在会在一个循环中调用这个方法，每次将上一次调用的结果作为
lastRemainder传回。/**
* The short division algorithm, like described in
* <a href="http://en.wikipedia.org/wiki/Short_division">Wikipedia's
* article <em>Short division</em></a>.
* @param result an array where we should put the quotient digits in.
* @param resultIndex the index in the array where the highest order digit
* should be put, the next digits will follow.
* @param divident the array with the divident's digits. (These will only
* be read, not written to.)
* @param dividentIndex the index in the divident array where we should
* start dividing. We will continue until the end of the array.
* @param divisor the divisor. This must be a number smaller than
* {@link #BASE}.
* @return the remainder, which will be a number smaller than
* {@code divisor}.
*/
private int divideDigits(int[] result, int resultIndex,
int[] divident, int dividentIndex,
int divisor) {
int remainder = 0;
for(; dividentIndex < divident.length; dividentIndex++, resultIndex++) {
remainder = divideDigit(result, resultIndex,
divident[dividentIndex],
remainder, divisor);
}
return remainder;
}
这个方法仍然返回一个整数，即余数。
现在我们想要一个返回DecimalBigInt的公共方法，因此我们创建了一个。它的任务是检查参数、为工作方法创建一个数组、丢弃余数并从结果中创建一个DecimalBigInt。（构造函数会移除可能存在的前导零。）
/**
* Divides this number by a small number.
* @param divisor an integer with {@code 0 < divisor < BASE}.
* @return the integer part of the quotient, ignoring the remainder.
* @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
*/
public DecimalBigInt divideBy(int divisor)
{
if(divisor <= 0 || BASE <= divisor) {
throw new IllegalArgumentException("divisor " + divisor +
" out of range!");
}
int[] result = new int[digits.length];
divideDigits(result, 0,
digits, 0,
divisor);
return new DecimalBigInt(result);
}
我们还有一个类似的方法，它返回余数：
/**
* Divides this number by a small number, returning the remainder.
* @param divisor an integer with {@code 0 < divisor < BASE}.
* @return the remainder from the division {@code this / divisor}.
* @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
*/
public int modulo(int divisor) {
if(divisor <= 0 || BASE <= divisor) {
throw new IllegalArgumentException("divisor " + divisor +
" out of range!");
}
int[] result = new int[digits.length];
return divideDigits(result, 0,
digits, 0,
divisor);
}
这些方法可以像这样调用：
DecimalBigInt d3_by_100 = d3.divideBy(100);
System.out.println("d3/100 = " + d3_by_100);
System.out.println("d3%100 = " + d3.modulo(100));
转换成任意进制
现在我们已经有了基础，可以将数字转换成任意进制。当然，并不是真正的任意进制，只允许使用小于BASE的进制，但这不应该是一个太大的问题。
如另一个关于数字转换的回答中所述，我们需要做的是“除法、余数、乘法、加法”。其中的“乘法-加法”实际上只是把单个数字组合在一起，因此我们可以用简单的数组访问来替代它。
由于我们总是需要商和余数，因此我们将不使用公共方法modulo和divideBy，而是重复调用divideDigits方法。
/**
* converts this number to an arbitrary radix.
* @param radix the target radix, {@code 1 < radix < BASE}.
* @return the digits of this number in the base-radix system,
* in big-endian order.
*/
public int[] convertTo(int radix)
{
if(radix <= 1 || BASE <= radix) {
throw new IllegalArgumentException("radix " + radix +
" out of range!");
}
首先，对于0的情况进行特殊处理。
// zero has no digits.
if(digits.length == 0)
return new int[0];
然后，我们创建一个足够长的用于存储结果数字的数组，以及其他一些变量。
// raw estimation how many output digits we will need.
// This is just enough in cases like BASE-1, and up to
// 30 digits (for base 2) too much for something like (1,0,0).
int len = (int) (Math.log(BASE) / Math.log(radix) * digits.length)+1;
int[] rDigits = new int[len];
int rIndex = len-1;
int[] current = digits;
int quotLen = digits.length;
quotLen 是上一次除法的商中数字数量（不包括前导零）。如果这个值为0，那么我们就完成了。
while(quotLen > 0) {
下一个商的新数组。
int[] quot = new int[quotLen];
取商和余数的操作。商现在存储在quot中，余数存储在rem中。
int rem = divideDigits(quot, 0,
current, current.length - quotLen,
radix);
我们将余数放入输出数组中（从最后一位开始填充）。
rDigits[rIndex] = rem;
rIndex --;
然后我们为下一轮交换这些数组。
current = quot;
如果商的最高位有前导零（最多只能有一个，因为基数小于BASE），我们会将商的长度减少一位。下一个数组将更小。
if(current[0] == 0) {
// omit leading zeros in next round.
quotLen--;
}
}
在循环后，rDigits数组中可能会有前导零，我们需要将它们去掉。
// cut of leading zeros in rDigits:
while(rIndex < 0 || rDigits[rIndex] == 0) {
rIndex++;
}
return Arrays.copyOfRange(rDigits, rIndex, rDigits.length);
}
就是这样。看起来有点复杂，不过下面是如何使用它的示例：
System.out.println("d4 in base 11: " +
Arrays.toString(d4.convertTo(11)));
System.out.println("d5 in base 7: " +
Arrays.toString(d5.convertTo(7)));
这些代码将打印出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] 和[1，2，3，4，5，6，0，1，2，3，4，5，6，0，1，2，3，4，5，6，0]，这些数字与我们之前解析的一样（不过是从字符串中解析出来的）。基于此，我们还可以将其格式化为字符串：
/**
* Converts the number to a String in a given radix.
* This uses {@link Character.digit} to convert each digit
* to one character.
* @param radix the radix to use, between {@link Character.MIN_RADIX}
* and {@link Character.MAX_RADIX}.
* @return a String containing the digits of this number in the
* specified radix, using '0' .. '9' and 'a' .. 'z' (as much as needed).
*/
public String toString(int radix) {
if(radix < Character.MIN_RADIX || Character.MAX_RADIX < radix) {
throw new IllegalArgumentException("radix out of range: " + radix);
}
if(digits.length == 0)
return "0";
int[] rdigits = convertTo(radix);
StringBuilder b = new StringBuilder(rdigits.length);
for(int dig : rdigits) {
b.append(Character.forDigit(dig, radix));
}
return b.toString();
}
- Paŭlo Ebermann
2
如果你想避免使用 BigInteger，并且要实现或研究一个与 binary-coded decimal 相关的库，你可能需要考虑一下。不过如果你想使用它，你可以用 BigInteger 来计算 90 的阶乘：
public static BigInteger factorial(BigInteger value) {
BigInteger total = BigInteger.ONE;
for (int i = 0; value.compareTo(BigInteger.ONE) == 1; i++) {
total = total.multiply(value);
value = value.subtract(BigInteger.ONE);
}
return total;
}
- WhiteFang34
1
啊，我刚意识到我在我的答案中实现了一种（紧缩的）二进制编码十进制 :-) - Paŭlo Ebermann
2
使用以下代码可以对任意长度的数字进行乘法运算：
public class BigNumberMultiplication {
private static int[] firstBigNumber = null;
private static int[] secondBigNumber = null;
public static int[] baseMul(int[] baseMultiple, int base) {
System.out.println("baseMultiple" + Arrays.toString(baseMultiple) + base);
for (int i = 0; i < baseMultiple.length; i++) {
baseMultiple[i] *= base;
}
System.out.println("basemultipleresultwithoutcarryforward" + baseMultiple);
return carryForward(baseMultiple);
}
public static int[] basePowerMul(int[] basePowerMultiple, int base, int power) {
int basePowerMultipleTemp[] = baseMul(basePowerMultiple, base);
System.out.println("basePowerMultipleTemp" + Arrays.toString(basePowerMultipleTemp) + "power" + power);
int basePowerMultipleResult[] = new int[basePowerMultipleTemp.length + (power - 1)];
for(int i = 0; i < basePowerMultipleTemp.length; i++)
basePowerMultipleResult[i] = basePowerMultipleTemp[i];
if(power > 1){
for(int i = 0; i < (power - 1); i++)
basePowerMultipleResult[basePowerMultipleTemp.length + i] = 0;
}
System.out.println("basepowermulresult" + Arrays.toString(basePowerMultipleResult));
return basePowerMultipleResult;
}
public static int[] addBigNumber(int[] finalNumberInArray, int[] finalNumberInArrayTemp){
System.out.println("final number in array" + Arrays.toString(finalNumberInArray) + "finalNumberInTemp" + Arrays.toString(finalNumberInArrayTemp));
int n = finalNumberInArray.length;
for(int i = (finalNumberInArrayTemp.length - 1); i >= 0; i--){
finalNumberInArray[n - 1] += finalNumberInArrayTemp[i];
n--;
}
return carryForward(finalNumberInArray);
}
public static int[] carryForward(int[] arrayWithoutCarryForward){
int[] arrayWithCarryForward = null;
System.out.println("array without carry forward" + Arrays.toString(arrayWithoutCarryForward));
for (int i = arrayWithoutCarryForward.length - 1; i > 0; i--) {
if (arrayWithoutCarryForward[i] >= 10) {
int firstDigit = arrayWithoutCarryForward[i] % 10;
int secondDigit = arrayWithoutCarryForward[i] / 10;
arrayWithoutCarryForward[i] = firstDigit;
arrayWithoutCarryForward[i - 1] += secondDigit;
}
}
if(arrayWithoutCarryForward[0] >= 10){
arrayWithCarryForward = new int[arrayWithoutCarryForward.length + 1];
arrayWithCarryForward[0] = arrayWithoutCarryForward[0] / 10;
arrayWithCarryForward[1] = arrayWithoutCarryForward[0] % 10;
for(int i = 1; i < arrayWithoutCarryForward.length; i++)
arrayWithCarryForward[i + 1] = arrayWithoutCarryForward[i];
}
else{
arrayWithCarryForward = arrayWithoutCarryForward;
}
System.out.println("array with carry forward" + Arrays.toString(arrayWithCarryForward));
return arrayWithCarryForward;
}
public static int[] twoMuscularNumberMul(){
int finalNumberInArray[] = null;
for(int i = 0; i < secondBigNumber.length; i++){
if(secondBigNumber[i] == 0){}
else {
int[] finalNumberInArrayTemp = basePowerMul(Arrays.copyOf(firstBigNumber, firstBigNumber.length), secondBigNumber[i], secondBigNumber.length - i);
if(finalNumberInArray == null){
finalNumberInArray = finalNumberInArrayTemp;
System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
}
else{
finalNumberInArray = addBigNumber(finalNumberInArray, finalNumberInArrayTemp);
System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
}
}
}
return finalNumberInArray;
}
public static int [] readNumsFromCommandLine() {
Scanner s = new Scanner(System.in);
System.out.println("Please enter the number of digit");
int count = s.nextInt();
System.out.println("please enter the nuumber separated by space");
s.nextLine();
int [] numbers = new int[count];
Scanner numScanner = new Scanner(s.nextLine());
for (int i = 0; i < count; i++) {
if (numScanner.hasNextInt()) {
numbers[i] = numScanner.nextInt();
} else {
System.out.println("You didn't provide enough numbers");
break;
}
}
return numbers;
}
public static void main(String[] args) {
firstBigNumber = readNumsFromCommandLine();
secondBigNumber = readNumsFromCommandLine();
System.out.println("1st number" + Arrays.toString(firstBigNumber) + "2nd number" + Arrays.toString(secondBigNumber));
int[] finalArray = twoMuscularNumberMul();
System.out.println(Arrays.toString(finalArray));
}
}
- user2130532
2
它可以将数字的任何位数相乘。尽情享受吧。 - user2130532
2欢迎来到Stackoverflow！请不要仅仅发布代码。如果您尝试通过解释来回答问题，那将更有帮助。 - Sebastian
1
当我想要进行90！或其他大量计算时，我尝试使用一个int[]数组，每个元素都保存一个数字。然后我应用传统的笔和纸乘法将答案存储在另一个int[]数组中。
这是我用Java编写的可以快速计算100!的代码。随意使用此代码。
这是我用Java编写的可以快速计算100!的代码。随意使用此代码。
public int factoial(int num) {
int sum = 0;
int[][] dig = new int[3][160];
dig[0][0] = 0;
dig[0][1] = 0;
dig[0][2] = 1;
for (int i = 99; i > 1; i--) {
int len = length(i);
for (int k = 1; k <= len; k++) { // Sets up multiplication
int pos = len - k;
dig[1][pos] = ((i / (int) (Math.pow(10, pos))) % 10);
}
int temp;
for (int k = 0; k < len; k++) { // multiplication
for (int j = 0; j < 159; j++) {
dig[2][k + j] += (dig[1][k] * dig[0][j]);
if (dig[2][k + j] >= 10) {
dig[2][k + j + 1] += dig[2][k + j] / 10;
dig[2][k + j] = dig[2][k + j] % 10;
}
}
}
sum = 0;
for (int k = 159; k >= 0; k--) {
System.out.print(dig[2][k]);
dig[0][k] = dig[2][k];
dig[1][k] = 0;
sum += dig[2][k];
dig[2][k] = 0;
}
System.out.println();
}
return sum;
}
- Adhyyan Sekhsaria
1
Java中使用运算符
这意味着如果你不能将所需数字装入
+，-，*，/和%进行算术运算受到Java基本数据类型的限制。这意味着如果你不能将所需数字装入
double或long的范围内，那么你必须使用“大数”库，如Java内置的（BigDecimal，BigInteger）或第三方库，或编写自己的库。这也意味着你不能使用算术运算符，因为Java不支持运算符重载。- maerics
0
如果我们要对非常大的数字进行算术运算，那么它们必须以某种对象形式存在，例如字符串。
假设有一些字符长度大于BigInteger范围的字符串。
在这种情况下，我将执行类似于笔记本电脑上的算术运算。例如-假设我们需要进行加法。从比较两个字符串的长度开始。创建三个新字符串。第一个字符串是较小的字符串。第二个字符串是长度等于较小字符串的长字符串的最右子字符串。第三个字符串是左侧剩余的长字符串。现在从末尾开始将第一个和第二个字符串相加，将字符转换为整数，每次保留进位在int变量中。在每次添加后立即将总和附加到StringBuffer中。在两个字符串相加后，对第三个字符串执行相同的操作，并继续添加进位。最后反转StringBuffer并返回String。
以下是我用于加法的代码
public String addNumber(String input1,String input2){
int n=0;String tempStr;
String one="";
String two="";
if(input1.length()>input2.length()){
n=input1.length()-input2.length();
tempStr=new String(input1);
one=new String(input1.substring(n,input1.length()));
two=new String(input2);
}else{
n=input2.length()-input1.length();
tempStr=new String(input2);
one=new String(input2.substring(n,input2.length()));
two=new String(input1);
}
StringBuffer temp=new StringBuffer();
for(int i=0;i<n;i++){
temp.append(tempStr.charAt(i));
}
StringBuffer newBuf=new StringBuffer();
int carry=0;
int c;
for(int i=one.length()-1;i>=0;i--){
int a=Character.getNumericValue(one.charAt(i));
int b=Character.getNumericValue(two.charAt(i));
c=a+b+carry;
newBuf.append(""+(c%10));
c=c/10;
carry=c%10;
}
String news=new String(temp);
for(int i=news.length()-1;i>=0;i--){
c=(Character.getNumericValue(news.charAt(i)))+carry;
newBuf.append(""+(c%10));
c=c/10;
carry=c%10;
}
if(carry==1){
newBuf.append(""+carry);
}
String newisis=new String(newBuf.reverse());
return newisis;
}
- Shubhdeep Singh
0
强调文本 public class BigInteger {
public static String checkSignWithRelational(int bigInt1, int bigInt2){
if( bigInt1 < 0){
return "negative";
}else {
return "positive";
}
}
BigInteger( long init)
{
Long.parseLong(bigInt1);
}
BigInteger String (String init){
return null;
}
private static int intLenght(int bigInt) {
return Integer.toString(bigInt).length();
}
private static int[] intToArray(int bigInt, int bigIntLength, int arrayLength) {
int array[] = new int[arrayLength ];
for (int i = 0; i < arrayLength ; i++) {
array[i] = ( i<bigIntLength ?
getDigitAtIndex(bigInt, bigIntLength - i -1) :0 );
}
return array;
}
static String add(int bigInt1, int bigInt2) {
//Find array length
int length1 = intLenght(bigInt1);
int length2 = intLenght(bigInt2);
int arrayLength = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, arrayLength);
int array2[] = intToArray(bigInt2, length2, arrayLength);
return add(array1, array2);
}
private static String add(int[] array1, int[] array2) {
int carry=0;
int addArray[] = new int[array1.length + 1];
for (int i = 0; i < array1.length; i++) {
addArray[i] = (array1[i] + array2[i] + carry) % 10 ;
carry = (array1[i] + array2[i] + carry) / 10;
}
addArray[array1.length] = carry;
return arrayToString(addArray);
}
private static int getDigitAtIndex(int longint,int index){
return Integer.parseInt(Integer.toString(longint).substring(index, index+1));
}
private static String arrayToString(int[] addArray) {
String add = "";
boolean firstNonZero = false;
for (int i = addArray.length-1; i >= 0 ; i--) {
if(!firstNonZero && (addArray[i]==0)){
continue;
} else{
firstNonZero=true;
}
add += addArray[i];
if((i%3 ==0)&&i!=0){ add +=",";} //formatting
}
String sumStr = add.length()==0?"0":add;
return sumStr;
}
public static String sub(int bigInt1, int bigInt2) {
int length1 = intLenght(bigInt1);
int length2 = intLenght(bigInt2);
int arrayLength = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, arrayLength);
int array2[] = intToArray(bigInt2, length2, arrayLength);
return sub(array1, array2);
}
private static String sub(int[] array1, int[] array2) {
int carry=0;
int sub[] = new int[array1.length + 1];
for (int i = 0; i < array1.length; i++) {
sub[i] = (array1[i] - array2[i] + carry) % 10 ; //sum digits + carry; then extract last digit
carry = (array1[i] - array2[i] + carry) / 10; //Compute carry
}
sub[array1.length] = carry;
return arrayToString(sub);
}
public static String mul(int bigInt1, int bigInt2) {
int length1 = intLenght(bigInt1), length2 = intLenght(bigInt2), length = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, length); int array2[] = intToArray(bigInt2, length2, length);
return mul(array1, array2);
}
private static String mul(int[] array1, int[] array2) {
int product[] = new int[array1.length + array2.length];
for(int i=0; i<array1.length; i++){
for(int j=0; j<array2.length; j++){
int prod = array1[i] * array2[j];
int prodLength = intLenght(prod);
int prodAsArray[] = intToArray(prod, prodLength, prodLength);
for (int k =0; k < prodAsArray.length; k++) {
product[i+j+k] += prodAsArray[k];
int currentValue = product[i+j+k];
if(currentValue>9){
product[i+j+k] = 0;
int curValueLength = intLenght(currentValue);
int curValueAsArray[] = intToArray(currentValue, curValueLength, curValueLength);
for (int l = 0; l < curValueAsArray.length; l++) {
product[i+j+k+l] += curValueAsArray[l];
}
}
}
}
}
return arrayToString(product);
}
public static int div(int bigInt1, int bigInt2) {
if ( bigInt2 == 0){
throw new ArithmeticException("Division by 0 is undefined:" + bigInt1+ "/" + bigInt2);
}
int sign = 1;
if(bigInt1 < 0) {
bigInt1 = -bigInt1;
sign = -sign;
}
if (bigInt2 < 0){
bigInt2 = -bigInt2;
sign = -sign;
}
int result =0;
while (bigInt1 >= 0){
bigInt1 -= bigInt2;
result++;
}
return (result - 1) * sign;
}
public static String check(String bigInt1, String bigInt2){
int difference;
StringBuilder first = new StringBuilder(bigInt1);
StringBuilder second = new StringBuilder(bigInt2);
if(bigInt1.length()> bigInt2.length()){
difference = bigInt1.length() - bigInt2.length();
for(int x = difference; x > 0; x--){
second.insert(0,"0");
}
bigInt2 = second.toString();
return bigInt2;
}else {
difference = bigInt2.length() - bigInt1.length();
for (int x = difference; x> 0; x--)
{
first.insert(0, "0");
}
bigInt1 = first.toString();
return bigInt1;
}
}
public static int mod(int bigInt1, int bigInt2){
int res = bigInt1 % bigInt2;
return (res);
}
public static void main(String[] args) {
int bigInt1 = Integer.parseInt("987888787");
int bigInt2 = Integer.parseInt("444234343");
System.out.println(bigInt1+" + "+bigInt2+" = "+add(bigInt1, bigInt2));
System.out.println(bigInt1+" - "+bigInt2+" = "+sub(bigInt1, bigInt2));
System.out.println(bigInt1+" * "+bigInt2+" = "+mul(bigInt1, bigInt2));
System.out.println(bigInt1+" / "+bigInt2+" = "+div(bigInt1, bigInt2));
System.out.println(bigInt1+" % "+bigInt2+" = "+mod(bigInt1, bigInt2));
}
}
- BBsal
2
2解释应该放在答案部分，而不是评论区。请添加更多的解释，仅有代码的答案并不是很有帮助。 - Mephy
这个 BigInteger 类的实现是否有任何不同于其他答案的贡献？ - Teepeemm
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接