7

我正在尝试使用整数数组在 JavaScript 中实现 BigInt 类型。现在每个都有一个 256 的上限。我已经完成了所有整数运算，但我不知道如何将 BigInt 转换为其字符串表示形式。当然，简单的方法是这样的：

BigInt.prototype.toString = function(base) {
    var s = '', total = 0, i, conv = [
        ,,
        '01',
        '012',
        '0123',
        '01234',
        '012345',
        '0123456',
        '01234567',
        '012345678',
        '0123456789',
        ,
        ,
        ,
        ,
        ,
        '0123456789abcdef'
    ];
    base = base || 10;

    for(i = this.bytes.length - 1; i >= 0; i--) {
        total += this.bytes[i] * Math.pow(BigInt.ByteMax, this.bytes.length - 1 - i);
    }

    while(total) {
        s = conv[base].charAt(total % base) + s;
        total = Math.floor(total / base);
    }

    return s || '0';
};

但是当 BigInts 实际上变大时，我将无法再通过添加进行转换。如何将 base-x 数组转换为 base-y 数组？

4

2 回答 2

1

请参阅我最近在此回答中给出的类似问题的示例（它适用于 base-10 到 base-3，但原理应该是可转移的）：C Fast base convert from decimal to ternary。

总之：

迭代输入数字，从低到高。对于每个数字位置，首先计算输出表示中的 1000....000 (base-256) （它是 256 的前一个幂的 256 倍）。然后将该结果乘以数字，并累积到输出表示中。

您将需要在输出表示中执行乘法和加法的例程。乘法例程可以写成加法例程。

请注意，我没有声称这种方法在任何方面都很快（我认为它的位数为O(n^2) ）；我敢肯定有比这在算法上更快的方法。

于 2011-05-03T23:25:42.600 回答
0

如果您准备比我现在更多地考虑数学思维，那么似乎有人已经解释了如何使用帕斯卡三角形转换数字表示：

http://home.ccil.org/~remlaps/DispConWeb/index.html

底部附近有指向源代码的链接。它们使用的是 Java 而不是 JavaScript，但是如果您正在努力学习数学，您可能会想出自己的实现或努力移植代码......

于 2011-05-03T23:33:18.200 回答