C++-100阶乘

Question

100阶乘怎么算才不会溢出

Answer 1

解决方法就是自己构造数据结构.

可以参考Java中BigInteger的实现.
1. 数据结构中包含 标志位, -1表示负数, 1表示正数, 0表示0.
2. 用一个int数组 表示 这个大数. java里的实现, 数组为mag, 那么mag[0]表示的位数最大, 就是说是反过来看的, 保证mag[0]不为0.

BigInteger中乘法的实现, 和我们平时手算乘法公式类似, 一位一位乘, 要考虑进位. 主要源码如下, 两个int数组相乘得到结果的int数组:

final static long LONG_MASK = 0xffffffffL;
private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
int xstart = xlen - 1;
int ystart = ylen - 1;

if (z == null || z.length < (xlen+ ylen))
z = new int[xlen+ylen];

long carry = 0;
for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) {
long product = (y[j] & LONG_MASK) *
(x[xstart] & LONG_MASK) + carry;
z[k] = (int)product;
carry = product >>> 32;
}
z[xstart] = (int)carry;

for (int i = xstart-1; i >= 0; i--) {
carry = 0;
for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {
long product = (y[j] & LONG_MASK) *
(x[i] & LONG_MASK) +
(z[k] & LONG_MASK) + carry;
z[k] = (int)product;
carry = product >>> 32;
}
z[i] = (int)carry;
}
return z;
}

拿到结果的int数组后, 去除开头的0.

回答@醉酒剑秋(33787218)的问题:

为什么0至xstart-1和xstart要分开，直接放在一个循环里面行不行？
: 这个手工在纸上计算一下543*434就知道, 首先计算543*4, 这里只需考虑每一位的乘, 加上上一次的进位即可; 接着算543*3, 需要考虑每一位的乘, 加上上一次的进位, 再加上 结果位上已有的值. 目测如果初始化结果数组z全为0, 则可以只用下面的那个循环来做; 但是现在两个循环明显效率要高一点点(第一个循环少了+(z[k] & LONG_MASK)), 在这种基础类里性能可是很重要的.
还有为什么或运算0xFFFFFFFFL？直接相乘可以吗
: 是与0xFFFFFFFFL, 注意0xFFFFFFFFL是long型, 这里是把int型转为与它数值相等的long; 否则直接int*int是会溢出的.

更新

还是有些要补充的地方:
1. java里是没有无符号数的, 所以int最大值为0x7fffffff(只用了31bit); 而在上面的程序中, 实际是把int当作了无符号数来用, 充分使用了这32个bit, 所以中间结果的int是作为 (int数)&0xffffffffL来使用的, 从java int型角度来说是会溢出的.
2. 中间结果的long值也是会溢出的, 所以这里用的是无符号右移>>>. -1>>>31 =1

Answer 2

可以查看高精度乘法，用数组存储，进行运算。

Answer 3

算的方法还是一样循环乘过去
重点是把结果存在一个数组里面（每位存一个数字），防止溢出