如何将Java long转换为字符串并保持自然顺序

Question

我目前在研究一个简单的编程问题，可能会很有趣，至少对于那些认为编程是艺术的人来说 :) 所以这是它：

如何最好地表示长整型为字符串，同时保持它们的自然顺序？

此外，字符串表示应该匹配^[A-Za-z0-9]+$。（我不太严格，但请避免使用控制字符或任何可能导致编码困扰、在 XML 中非法、具有换行符或类似字符的内容，这些肯定会引起问题）

这是一个 JUnit 测试用例：

@Test
public void longConversion() {
    final long[] longs = { Long.MIN_VALUE, Long.MAX_VALUE, -5664572164553633853L,
            -8089688774612278460L, 7275969614015446693L, 6698053890185294393L,
            734107703014507538L, -350843201400906614L, -4760869192643699168L,
            -2113787362183747885L, -5933876587372268970L, -7214749093842310327L, };

    // keep it reproducible
    //Collections.shuffle(Arrays.asList(longs));

    final String[] strings = new String[longs.length];
    for (int i = 0; i < longs.length; i++) {
        strings[i] = Converter.convertLong(longs[i]);
    }

    // Note: Comparator is not an option
    Arrays.sort(longs);
    Arrays.sort(strings);

    final Pattern allowed = Pattern.compile("^[A-Za-z0-9]+$");
    for (int i = 0; i < longs.length; i++) {
        assertTrue("string: " + strings[i], allowed.matcher(strings[i]).matches());
        assertEquals("string: " + strings[i], longs[i], Converter.parseLong(strings[i]));
    }
}

以下是我正在寻找的方法：

public static class Converter {
    public static String convertLong(final long value) {
        // TODO
    }

    public static long parseLong(final String value) {
        // TODO
    }
}

我已经有一些解决这个问题的想法了，但我认为可能会从社区中得到一些好的（有创意的）建议。

此外，如果这个转换：

• 尽可能短
• 易于在其他语言中实现

编辑：我很高兴看到两位非常有声望的程序员遇到了和我一样的问题：使用“-”表示负数无法正常工作，因为“-”不能改变排序顺序：

1. -0001
2. -0002
3. 0000
4. 0001
5. 0002

- sfussenegger

Answer 1

好的，重来：

class Converter {
  public static String convertLong(final long value) {
    return String.format("%016x", value - Long.MIN_VALUE);
  }

  public static long parseLong(final String value) {
    String first = value.substring(0, 8);
    String second = value.substring(8);
    long temp = (Long.parseLong(first, 16) << 32) | Long.parseLong(second, 16);
    return temp + Long.MIN_VALUE;
  }
}

这个问题需要一些解释。首先，让我证明它是可逆的，而且结果的转换应该显示出顺序：

for (long aLong : longs) {
  String out = Converter.convertLong(aLong);
  System.out.printf("%20d %16s %20d\n", aLong, out, Converter.parseLong(out));
}

输出：

-9223372036854775808 0000000000000000 -9223372036854775808
 9223372036854775807 ffffffffffffffff  9223372036854775807
-5664572164553633853 316365a0e7370fc3 -5664572164553633853
-8089688774612278460 0fbba6eba5c52344 -8089688774612278460
 7275969614015446693 e4f96fd06fed3ea5  7275969614015446693
 6698053890185294393 dcf444867aeaf239  6698053890185294393
  734107703014507538 8a301311010ec412   734107703014507538
 -350843201400906614 7b218df798a35c8a  -350843201400906614
-4760869192643699168 3dedfeb1865f1e20 -4760869192643699168
-2113787362183747885 62aa5197ea53e6d3 -2113787362183747885
-5933876587372268970 2da6a2aeccab3256 -5933876587372268970
-7214749093842310327 1be00fecadf52b49 -7214749093842310327

正如你所看到的，Long.MIN_VALUE和Long.MAX_VALUE（前两行）是正确的，其他值基本上也符合要求。

这是做什么的？

假设有符号字节值，你有：

• -128 => 0x80
• -1 => 0xFF
• 0 => 0x00
• 1 => 0x01
• 127 => 0x7F

现在，如果你将0x80添加到这些值中，你会得到：

• -128 => 0x00
• -1 => 0x7F
• 0 => 0x80
• 1 => 0x81
• 127 => 0xFF

这是正确的顺序（带有溢出）。

以上基本上是使用64位有符号长整型而不是8位有符号字节执行此操作的过程。

回转换有点复杂。你可能会认为可以使用：

return Long.parseLong(value, 16);

但是你不能将16个f传递给该函数(-1)，否则它会抛出异常。它似乎将其视为无符号十六进制值，而long无法容纳。因此，我将其分成两半并解析每个部分，将它们组合在一起，左移第一半32位。

- cletus

---

我会使用 String.format...哦，还有缺少线程（不）安全的免责声明。 - user85421

@Int：你可以使用String.format，但是你需要解析它以便进行双向转换，所以最好使用一个方法完成。 - cletus

@sfuss：现在已经更正了。然而，给你诚恳回答的人投反对票通常意味着他们不会再帮助你。如果我已经达到声望上限或者根本不感兴趣，通常我会在面对基本上是不感激的情况下删除我的回答并继续前进。 - cletus

@cletus，你的回答是错误的，因此我给了一个负评。不过，在你修正后，我将其改为了一个赞，并接受了你的回答。这不就是它应该运作的方式吗？ - sfussenegger

@sfuss：也许只是我个人的想法，我并不是因为被激怒了才这么说。这只是一些建议，帮助你获得更好的回答。就我个人而言，如果一个回答有错别字或者是出于善意但是错误的回答，我是不会给它点踩的。点踩有点像是责备。当你请求别人帮忙时，责备并不能促进更多的帮助。但这可能只是我的个人看法。 - cletus

Answer 2

编辑：好吧，仅为负数添加负号是不起作用的...但您可以将值转换为效果上为“无符号”的长整型，使得Long.MIN_VALUE映射到“0000000000000000”，而Long.MAX_VALUE映射到“FFFFFFFFFFFFFFFF”。难以阅读，但会得到正确的结果。

基本上，您只需要在将值转换为十六进制之前加上2^63 - 但由于Java没有无符号长整型，因此这可能在Java中稍微有些麻烦...使用BigInteger可能是最简单的方法：

private static final BigInteger OFFSET = BigInteger.valueOf(Long.MIN_VALUE)
                                                   .negate();

public static String convertLong(long value) {
    BigInteger afterOffset = BigInteger.valueOf(value).add(OFFSET);
    return String.format("%016x", afterOffset);
}

public static long parseLong(String text) {
    BigInteger beforeOffset = new BigInteger(text, 16);
    return beforeOffset.subtract(OFFSET).longValue();
}

诚然，这并不是特别高效的方法，但它适用于你所有的测试用例。

- Jon Skeet

---

@cletus：我哪里没有代码？ :) （是的，在您发表评论之前，它就已经在那里了 :) - Jon Skeet

@Jon：看吧，如果你要对一个包含20亿个long类型元素的数组进行处理，我的代码会更快。 :) - cletus

现在它可以工作了，太棒了。不过我会采用Cletus的解决方案，因为它更短。干杯！ - sfussenegger

@sfussenegger: 我用了 Cletus 的格式字符串，这使得我的代码更短了 :) - Jon Skeet

@Jon 现在有点难决定。就长度而言，这两个解决方案是相似的。同时，Cletus 的应该更快，但你的对较短的输入（即非 16 个字符的字符串）更容忍...我想这将是一个不眠之夜 :) - sfussenegger

Answer 3

如果您不需要可打印的字符串，您可以在将值左移 Long.MIN_VALUE (-0x80000000) 以模拟无符号长整型之后，在四个字符中编码长整型：

public static String convertLong(long value) {
    value += Long.MIN_VALUE;
    return "" + 
        (char)(value>>48) + (char)(value>>32) + 
        (char)(value>>16) + (char)value; 
}

public static long parseLong(String value) {
    return (
        (((long)value.charAt(0))<<48) + 
        (((long)value.charAt(1))<<32) + 
        (((long)value.charAt(2))<<16) + 
        (long)value.charAt(3)) + Long.MIN_VALUE;
}

使用代理对不会有问题，因为字符串的自然顺序是由其字符中的UTF-16值而不是UCS-2代码点值定义的。

- jarnbjo

---

抱歉，虽然这个方法可以工作，但它使用了不可打印字符，这并不是一个选项。我已经编辑了我的问题以包括这个要求。 - sfussenegger

所以在我考虑其他解决方案之前，您能否与我们分享“可打印”的定义？这些都是具有有效Unicode代码点、ISO-8859-1或仅限ASCII的所有字符吗？空格字符是否可打印？ - jarnbjo

我希望看到一些不会引起编码问题的东西，适合放在一行中，并且与XML或CSV表示良好地配合。[A-Za-Z0-9]应该是一个明智的选择，但如果需要，可以添加更多。我对此要求并不太严格。例如，使用0x00作为字符肯定会引起麻烦，必须避免。 - sfussenegger

Answer 4

RFC2550中有一种技术——一个关于4位日期的Y10K问题的愚人节RFC，可以应用于此目的。基本上，每当整数的字符串表示增长需要另一个数字时，就会在前面添加另一个字母或其他（可打印）字符以保留所需的排序顺序。负规则更加深奥，产生的字符串更难以一眼读懂...但在代码中仍然很容易应用。

对于正数来说，它们仍然是可读的。

请参见：

http://www.faqs.org/rfcs/rfc2550.html

- gojomo