有没有更快的方法将十六进制小数部分转换为十进制？

Question

我编写了一个程序，可以生成十六进制的圆周率数字。每隔一段时间，在基准值下，我想将我拥有的十六进制值转换为十进制值并将其保存到文件中。目前我正在使用 BigDecimal 通过以下代码进行计算：

private static String toDecimal(String hex) {
    String rawHex = hex.replace(".", "");
    BigDecimal base = new BigDecimal(new BigInteger(rawHex, 16));
    BigDecimal factor = new BigDecimal(BigInteger.valueOf(16).pow(rawHex.length() - 1));
    BigDecimal value = base.divide(factor);
    return value.toPlainString().substring(0, hex.length());
}

请注意，此方法仅适用于整数部分包含一位的十六进制值，包括 pi，请勿复制粘贴以供一般使用。

所以这段代码工作正常，但对于最新的基准测试，250 万位数字，转换需要 11.3 小时才能完成。

有没有更快的手动方式？

我尝试将第一个小数位除以 16，将第二个小数位除以 16^2，等等，但这很快就会失控。也许有某种方法可以将数字移回位以保持除数较低？但可能需要处理 n+1、n+2、n+3 等数字以获得 n 的正确值。

Answer 1

首先，我认为你的函数 toDecimal 是错误的，因为它没有正确转换输入 ".1a"（它被关闭了 16 倍），例如，并抛出输入异常".800"。第三行应该是：

BigDecimal factor = new BigDecimal(BigInteger.valueOf(16).pow(rawHex.length()));

异常产生于：

return value.toPlainString().substring(0, hex.length());

转换后的值可能比输入值短，您会得到 java.lang.StringIndexOutOfBoundsException。

继续：

事实上，我没有根据您当前的方法对它进行基准测试；我只是将此作为“思考的食物”。我在这里做乘法，因为 child 在学校被教导这样做，在你的情况下，我们有一个大循环来产生一个数字。但是如果你能以某种方式调整它以使用 BigDecimal（目前还不清楚你会怎么做）它可能比你当前的方法更快（真正需要的是 BigHexadecimal class）。

可以看出，可以使用乘法将分数从一个基数转换为另一个基数。在这种情况下，我们有以下十六进制小数（我们可以忽略整数部分，在转换 pi 时为 3）：

.h₁h₂h₃h₄ ... h_n

其中 h_n 是第 n^th 个十六进制“半字节”。

我们希望将以上转换为以下小数：

.d₁d₂d₃d₄ ... d_n

其中 d_n 是第 n^th 个十进制数字。

如果我们将两个数量都乘以 10，我们将得到：

h^'₁.h^'₂h^'₃h^'₄ ... h^'_n
素数 (^`) 表示乘法后我们有全新的十六进制半字节值。

和

d₁.d₂d₃d₄ ... d_n
乘以 10 只是将小数点向左移动一位。

注意小数点左边的数量必须相等，即d₁ == h^'₁。因此，我们反复将十六进制小数乘以 10，每次乘以整数部分作为转换的下一个十进制数字。我们重复此操作，直到我们的新十六进制分数变为 0 或产生了任意数量的十进制数字：

See Java Demo

class Test {

    private static String toDecimal(String hex, int numberDigits) {
        /* converts a string such as "13.1a" in base 16 to "19.1015625" in base 10 */
        int index = hex.indexOf('.');
        assert index != -1;
        StringBuilder decimal = new StringBuilder((index == 0) ? "" : String.valueOf(Integer.parseInt(hex.substring(0, index), 16)));
        decimal.append('.');
        int l = hex.length() - index - 1;
        assert l >= 1;
        int firstIndex = index + 1;
        int hexDigits[] = new int[l];
        for (int i = 0; i < l; i++) {
            hexDigits[i] = Integer.parseInt(hex.substring(i + firstIndex, i + firstIndex + 1), 16);
        }
        while (numberDigits != 0 && l != 0) {
            int carry = 0;
            boolean allZeroes = true;
            for (int i = l - 1; i >= 0; i--) {
                int value = hexDigits[i] * 10 + carry;
                if (value == 0 && allZeroes) {
                    l = i;
                }
                else {
                    allZeroes = false;
                    carry = (int)(value / 16);
                    hexDigits[i] = value % 16;
                }
            }
            numberDigits--;
            if (carry != 0 || (numberDigits != 0 && l != 0))
                decimal.append("0123456789".charAt(carry));
        }
        return decimal.toString();
    }

    public static void main(String[] args) {
        System.out.println(toDecimal("13.1a", 15));
        System.out.println(toDecimal("13.8", 15));
        System.out.println(toDecimal("13.1234", 15));
    }

}

打印：

19.1015625
19.5
19.07110595703125

Answer 2

感谢@Booboo 解决了这个问题。我对他的代码进行了一些改进，因此它应该适用于所有情况。我想 post 在这里供以后的访客使用。

/**
 * Converts a hex number string to a decimal number string.
 *
 * @param hex      The hex number string.
 * @param accuracy The number of decimal places to return in the decimal number string.
 * @return The decimal number string.
 */
public static String hexToDecimal(String hex, int accuracy) {
    if (!hex.matches("[0-9A-Fa-f.\-]+") || (accuracy < 0)) {
        return "";
    }
    
    boolean negative = hex.startsWith("-");
    hex = hex.replaceAll("^-", "");
    String integral = hex.contains(".") ? hex.substring(0, hex.indexOf(".")) : hex;
    String fraction = hex.contains(".") ? hex.substring(hex.indexOf(".") + 1) : "";
    if (integral.contains("-") || fraction.contains(".") || fraction.contains("-")) {
        return "";
    }
    
    StringBuilder decimal = new StringBuilder();
    decimal.append(negative ? "-" : "");
    decimal.append(integral.isEmpty() ? "0" : new BigDecimal(new BigInteger(integral, 16)).toPlainString());
    if (fraction.isEmpty() || (accuracy == 0)) {
        return decimal.toString();
    }
    decimal.append(".");
    
    int numberDigits = accuracy;
    int length = Math.min(fraction.length(), numberDigits);
    int[] hexDigits = new int[numberDigits];
    Arrays.fill(hexDigits, 0);
    IntStream.range(0, length).boxed().parallel().forEach(i -> hexDigits[i] = Integer.parseInt(String.valueOf(fraction.charAt(i)), 16));
    
    while ((numberDigits != 0)) {
        int carry = 0;
        for (int i = length - 1; i >= 0; i--) {
            int value = hexDigits[i] * 10 + carry;
            carry = value / 16;
            hexDigits[i] = value % 16;
        }
        decimal.append(carry);
        numberDigits--;
    }
    return decimal.toString();
}

/**
 * Converts a hex number string to a decimal number string.
 *
 * @param hex The hex number string.
 * @return The decimal number string.
 * @see #hexToDecimal(String, int)
 */
public static String hexToDecimal(String hex) {
    String fraction = hex.contains(".") ? hex.substring(hex.indexOf(".") + 1) : "";
    return hexToDecimal(hex, fraction.length());
}

public static void main(String[] args) {
    //integer
    Assert.assertEquals("0", hexToDecimal("0"));
    Assert.assertEquals("1", hexToDecimal("1"));
    Assert.assertEquals("9", hexToDecimal("9"));
    Assert.assertEquals("15", hexToDecimal("F"));
    Assert.assertEquals("242", hexToDecimal("F2"));
    Assert.assertEquals("33190", hexToDecimal("81A6"));
    Assert.assertEquals("256", hexToDecimal("100"));
    Assert.assertEquals("1048576", hexToDecimal("100000"));
    Assert.assertEquals("5191557193152165532727847676938654", hexToDecimal("FFF6AA0322BC458D5D11A632099E"));
    Assert.assertEquals("282886881332428154466487121231991859970997056152877088222", hexToDecimal("B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE"));
    Assert.assertEquals("-256", hexToDecimal("-100"));
    Assert.assertEquals("-144147542", hexToDecimal("-8978456"));
    Assert.assertEquals("-332651442596728389665499138728075237402", hexToDecimal("-FA42566214321CC67445D58EE874981A"));
    Assert.assertEquals("33190", hexToDecimal("81a6"));

    //decimal
    Assert.assertEquals("0.10", hexToDecimal("0.1a"));
    Assert.assertEquals("0.5", hexToDecimal("0.8"));
    Assert.assertEquals("0.0711", hexToDecimal("0.1234"));
    Assert.assertEquals("0.528966901", hexToDecimal("0.876A5FF4A"));
    Assert.assertEquals("-0.528966901", hexToDecimal("-0.876A5FF4A"));
    Assert.assertEquals("-0.00000000", hexToDecimal("-0.00000001"));
    Assert.assertEquals("-0.62067648792835838863907521427468", hexToDecimal("-0.9EE4A7810C666FF7453D06A44621030E"));
    Assert.assertEquals("0.528966901", hexToDecimal("0.876a5ff4a"));
    Assert.assertEquals("0.528966901", hexToDecimal(".876a5ff4a"));
    Assert.assertEquals("-0.528966901", hexToDecimal("-.876a5ff4a"));

    //combined
    Assert.assertEquals("15.33693", hexToDecimal("F.56412"));
    Assert.assertEquals("17220744.33934412", hexToDecimal("106C488.56DF41A2"));
    Assert.assertEquals("282886881332428154466487121231991859970997056152877088222.62067648792835838863907521427468", hexToDecimal("B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE.9EE4A7810C666FF7453D06A44621030E"));
    Assert.assertEquals("-17220744.33934412", hexToDecimal("-106C488.56DF41A2"));
    Assert.assertEquals("-282886881332428154466487121231991859970997056152877088222.62067648792835838863907521427468", hexToDecimal("-B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE.9EE4A7810C666FF7453D06A44621030E"));
    Assert.assertEquals("-17220744.33934412", hexToDecimal("-106c488.56df41a2"));
    Assert.assertEquals("3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97"));

    //accuracy
    Assert.assertEquals("-0.00000", hexToDecimal("-0.00000001", 5));
    Assert.assertEquals("-0.000000000232830", hexToDecimal("-0.00000001", 15));
    Assert.assertEquals("-0", hexToDecimal("-0.00000001", 0));
    Assert.assertEquals("282886881332428154466487121231991859970997056152877088222.5", hexToDecimal("B897A12C89896321C454A7DD9E150233CBB87A9F0233DDE.9EE4A7810C666FF7453D06A44621030E", 1));
    Assert.assertEquals("3.14", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97", 2));
    Assert.assertEquals("3.1415926535", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97", 10));
    Assert.assertEquals("3.1415926535897932384626433", hexToDecimal("3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0AC29B7C97", 25));

    //invalid
    Assert.assertEquals("", hexToDecimal("0.00000.001"));
    Assert.assertEquals("", hexToDecimal("0.00000-001"));
    Assert.assertEquals("", hexToDecimal("156-081.00000001"));
    Assert.assertEquals("", hexToDecimal("hello"));
    Assert.assertEquals("", hexToDecimal("9g"));
    Assert.assertEquals("", hexToDecimal("9G"));
    Assert.assertEquals("", hexToDecimal("546.FDA", -1));
    Assert.assertEquals("", hexToDecimal("546.FDA", -999));
}

有没有更快的方法将十六进制小数部分转换为十进制？

Is there a faster way to convert a hexadecimal fractional part to a decimal one?

java

algorithm

hex

base