java - 如何将用作一种 BigInteger 的 int 数组转换为 "human readable"字符串？

Question

我正在尝试实现 BigInteger 的一些功能作为个人编程练习。

像许多实现一样，我使用 int[]作为无符号整数。

我想实现基本功能，如加法、减法、乘法、除法，但我遇到了需要获得“人类可读”的问题 toString出于调试目的从我的数据结构中删除，以便我可以更好地检查和理解我在做什么。

我觉得我被卡住了。我不确定我的算法是否正确，但我无法检查它。

我查看了一些实现，如 Apache Harmony 或 OpenJDK，但它们用于创建字符串的算法看起来比加号、减号等的实际实现更复杂。

当然，我可以只使用那些复杂的其中之一，但如果我自己已经无法实现它，我至少希望能够理解它的实现。

有人可以建议一个简单的实现来转换 int[]到一个字符串？

示例:new int[]{Integer.MAX_VALUE, 1}应该被视为一个大的无符号数并打印:8589934590 (所以基本上是 2³³)。

Answer 1

我会使用这种方法:

你没有提到你如何存储零；它可能需要特殊处理，在这种情况下，您可以在继续算法的其余部分之前对其进行特殊处理。

复制 int[] ;叫它iArr .该算法的其余部分将在 iArr 上运行.

创建一个 char[] — 叫它 s ——够大了。从 int最多可以有十位数字，您可以使用 s = new char[iArr.length * 10] .

从位置 int i = s.length - 1 开始.去通过 iArr ，除以十，并将余数加上 '0' 存储起来在 s[i] .然后递减i .重复这个过程直到 iArr为零。 (除以十的逻辑大致是:将每个元素除以十，注意余数。将该余数乘以 Integer.MAX_INT + 1 加到下一个元素，然后将该元素除以十。不用说，您需要用 long 做你的数学计算。)

您的结果是 new String(s, i, s.length - i) .

为了效率:

您可以潜在地除以十的幂，例如 1000000或者诸如此类，一次获得一堆数字(显然，这使得 char 处理更加棘手)。

当您将 iArr 的主要元素归零时，您可以跟踪第一个非零元素的位置，并忽略在此之前的任何元素。

但实际上这些都不是必需的。

编辑添加 实际代码。这个程序:

public class Main
{
    private static final long RADIX = -2L * (long)Integer.MIN_VALUE;

    public static void main(final String... args)
    {
        System.out.println(stringify(new int[]{0})); // 0
        System.out.println(stringify(new int[]{1})); // 1
        System.out.println(stringify(new int[]{Integer.MAX_VALUE})); // 2^31-1
        System.out.println(stringify(new int[]{Integer.MIN_VALUE})); // 2^31
        System.out.println(stringify(new int[]{-1})); // 2^32-1
        System.out.println(stringify(new int[]{1, 0})); // 2^32
        System.out.println(stringify(new int[]{1, -1})); // 2^33-1
        System.out.println(stringify(new int[]{-1, -1})); // 2^64-1
        System.out.println(stringify(new int[]{1, 0, 0})); // 2^64
    }

    private static String stringify(final int[] _iArr)
    {
        final int[] iArr = new int[_iArr.length];
        System.arraycopy(_iArr, 0, iArr, 0, _iArr.length);
        final char[] ret = new char[10 * iArr.length];
        int retIndex = ret.length;
        while(true)
        {
            boolean isZero = true;
            int carry = 0;
            for(int i = 0; i < iArr.length; ++i)
            {
                long val = unsignedInt2Long(iArr[i]);
                if(val != 0L)
                    isZero = false;
                val += carry * RADIX;
                carry = (int) (val % 10L);
                val /= 10L;
                iArr[i] = long2UnsignedInt(val);
            }
            if(isZero)
            {
                if(retIndex == ret.length)
                    return "0";
                else
                    return new String(ret, retIndex, ret.length - retIndex);
            }
            assert(retIndex > 0);
            ret[--retIndex] = (char) (carry + (int)'0');
        }
    }

    private static long unsignedInt2Long(final int unsignedInt)
    {
        if(unsignedInt >= 0)
            return unsignedInt;
        else
            return unsignedInt + RADIX;
    }

    private static int long2UnsignedInt(final long _long)
    {
        assert(_long >= 0L);
        assert(_long < RADIX);
        if(_long <= (long) Integer.MAX_VALUE)
            return (int) _long;
        else
            return (int) (_long - RADIX);
    }
}

打印这个:

0
1
2147483647
2147483648
4294967295
4294967296
8589934591
18446744073709551615
18446744073709551616

(但您必须检查 main 方法及其注释，以确认我已正确理解您打算如何存储这些整数。)