Java BigInteger，截掉最后一位数字

Question

相当简单，如果 BigInteger 数字是 543，我希望它截掉最后一位数字，使其变为 54。

执行此操作的两种简单方法可以是：

1. 使用字符串、获取子字符串并使用新值创建新的 biginteger。
2. 对数字 10 使用 BigIntegers 除法。( 543 / 10 = 54.3 => 54 )

当然，我将使用大整数很多执行此操作。

我的猜测是，使用字符串会更慢，但话又说回来，我没有太多使用大整数，也不知道“除法”操作有多昂贵。

速度在这里至关重要，实现此目的最快的方法是什么（内存没有问题，只有速度）？

也欢迎其他解决方案。

Answer 1

除以 10 很可能会更快。

Answer 2

除以 10 比使用子字符串运算要快得多。 使用以下基准测试，我得到了大约 161 倍（比率与位数成正比）

    long divTime = 0;
    long substrTime = 0;
    final int bitsCount = 1000;

    for (int i = 0; i < 1000; ++i) {
        long t1, t2;
        BigInteger random = new BigInteger(bitsCount, new Random());

        t1 = System.currentTimeMillis();
        random.divide(BigInteger.TEN);
        t2 = System.currentTimeMillis();
        divTime += (t2 - t1);

        t1 = System.currentTimeMillis();
        String str = random.toString();
        new BigInteger(str.substring(0, str.length() - 1));
        t2 = System.currentTimeMillis();
        substrTime += (t2 - t1);
    }

    System.out.println("Divide: " + divTime);
    System.out.println("Substr: " + substrTime);
    System.out.println("Ratio:  " + (substrTime / divTime));

Answer 3

如果您静态创建一个数字为 10 的 BigInteger，然后用它除以 10，这可能是最快的方法。 它胜过每次创建一个临时的新 BigInteger。

子字符串的问题在于，您实际上每次都会创建一个新的字符串，而且速度要慢得多，更不用说迭代字符串以获取其子字符串的速度了。

Answer 4

最快的方法是通过高效的内部除法实现将数字除以 10。 该操作的内部原理在幕后，但肯定很重要，因为数字是以 2 为基数存储的。

Answer 5

最快的实现可能是使用内部表示以 10 为基数的数据类型，即某种 BCD。 然后，除以 10 只是意味着删除最后一个字节（或者甚至只是递增/递减索引，如果你以正确的方式实现它）。

当然，您必须从头开始实现所需的所有算术和其他操作，这使得工作量很大。

Answer 6

现在问这个问题可能还为时过早。 以显而易见的方式进行（除以十），然后对其进行基准测试，并在需要时进行优化。 转换为字符串表示形式并返回会慢得多。

Answer 7

单独的 toString() 可能比子字符串慢。

Answer 8

很多人都说除以 10 比转换为字符串并获取子字符串更快。 要理解原因，只需考虑一下从 BigInteger 转换为 String 所涉及的计算，反之亦然。 例如：

/* simplified pseudo code for converting +ve numbers to strings */
StringBuffer sb = new StringBuffer(...);
while (number != 0) {
   digit = number % 10;
   sb.append((char)(digit + '0'));
   number = number / 10;
}
return sb.toString();

需要注意的重要一点是，从数字转换为字符串需要重复除以 10。实际上，除法次数与 log10(number) 成正比。 另一个方向涉及 log10(number) 乘法。 很明显，这比单次除以 10 的计算量要大得多。

Answer 9

如果性能至关重要...不要使用 java

在编译为机器代码的语言（例如 c 或 c++）中，整数除法速度要快得多。 字符串操作使用（或可以使用）内存分配，因此速度很慢。

我敢打赌，在 java 中 int 除法也会更快。 否则他们的虚拟机实现真的很奇怪。