代码之家 › 专栏 › 技术社区 › sfussenegger

如何在保持自然顺序的同时将Java long转换为字符串

sorting algorithm java

sfussenegger · 技术社区 · 16 年前

我目前正在研究一个简单的编程问题,优化这个问题可能会很有趣——至少对那些相信编程是艺术的人来说是这样:)所以这里是:

如何最好地将长字符串表示为字符串,同时保持其自然顺序?

另外,字符串表示应该匹配 ^[A-Za-z0-9]+$ . (我在这里不太严格,但要避免使用控制字符或任何可能导致编码问题、在XML中是非法的、有换行符或肯定会导致问题的类似字符)

@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
    }
}

我已经对如何解决这个问题有了一些想法。不过,我想我可能会从社区得到一些好的(创造性的)建议。

尽可能短
易于用其他语言实现

编辑:我很高兴看到两个非常有声望的程序员遇到了和我一样的问题:用“-”来表示负数是行不通的,因为“-”不能颠倒排序顺序:

-0001
0001
0002

4 回复 | 直到 16 年前

cletus 16 年前

好的,拿两个:

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型
1=大于;0x81号

顺序正确(溢出)。

基本上,上面的方法是使用64位有符号长字节而不是8位有符号字节。

转换回来有点迂回。您可能认为可以使用:

return Long.parseLong(value, 16);

但你不能。向该函数(-1)传入16个f,它将引发异常。它似乎将其视为一个无符号的十六进制值 long

Jon Skeet 16 年前

编辑:好的,所以只给负数加负号是行不通的。。。但是您可以将该值转换为有效的“无符号”long,这样long.MIN\u值映射到“000000000000000”,long.MAX\u值映射到“ffffffffffff”。更难阅读,但会得到正确的结果。

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();
}

jarnbjo 16 年前

如果不需要可打印的字符串,可以在将值移位long.MIN\u值(-0x80000000)后将long编码为四个字符,以模拟无符号long:

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码点值定义的。

gojomo 15 年前

RFC2550中有一种技术——一个4月1日的RFC笑话,讲的是4位数日期的Y10K问题——可以应用于这个目的。本质上,每当整数的字符串表示增长到需要另一个数字时,就会在前面加上另一个字母或其他(可打印的)字符,以保留所需的排序顺序。消极的规则更神秘,产生的字符串更难一眼就读懂。。。但仍然很容易在代码中应用。

很好,对于正数,它们仍然可读。

请参见:

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