如何将用作 BigInteger 类型的 int 数组转换为“人类可读的”数组细绳？

Question

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

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

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

我感觉我被困住了。我不确定我的算法是否正确，但我没有办法检查它。

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

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

有人可以建议一个将 int[] 转换为 String 的简单实现吗？

示例：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，除以 10，并将余数加上 '0' 存储在 s[i] 中。然后递减i。重复此过程，直到 iArr 为零。 （除以 10 的逻辑大致是：将每个元素除以 10，记下余数。将余数乘以 Integer.MAX_INT + 1 添加到下一个元素，然后除那个< /em> 元素乘以十。不用说，您需要使用 long 进行数学计算。）
• 您的结果是 new String(s, i, s.length - i)< /代码>。

为了提高效率：

• 您可以除以 10 的幂，例如 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 方法及其注释，以确认我已正确理解您打算如何存储这些整数。）

Answer 2

首先实现十六进制转换器，并在开发的初始阶段使用十六进制作为人类可读的格式。执行十六进制很容易，因为您不需要实现除法：只需将各个项目转换为十六进制，将它们粘合在一起，就完成了。

一旦您的除法算法到位，您就可以通过通常的“获取余数 % 10 并除掉”方法实现到十进制格式的转换。