logo标签列表

如何将Java long转换为*无符号的*基X字符串（以及反向转换）？

javabigintegerunsignedbase36
3

[编辑] 在回答问题之前，请确实“阅读”问题，我不接受任何涉及BigInteger或其他类似低效方法的答案！

Java非常让人恼火的是，它不支持无符号数类型。您可以通过使用下一个更大的类型将byte、short或int转换为无符号类型，例如：

short s = -10;
int unsigned_short = s & 0xFFFF;

但是你不能使用long类型进行此操作，因为没有更大的类型。

那么，如何将有符号的long转换为“无符号”的基数X（在我的情况下为基数36），然后再转回来？Long类有这些方法，但是它们将long视为有符号的，仅仅因为它们是有符号的。

我可以使用一些操作和BigInteger来做到这一点，但是BigInteger非常慢，并且通过临时创建BigInteger而产生垃圾。而我将要进行很多这样的转换（我想）。我需要一个算法，它与Long.toString(long i, int radix)的默认实现一样高效。

试图调整Long.toString()代码，我得到了：

final int RADIX = 36;
final char[] DIGITS = { '0', ... , 'Z' };
long value = 100;
if (value == 0) {
    return "0";
} else {
    char[] buf = new char[13];
    int charPos = 12;
    long i = value;
    while (i != 0) {
        buf[charPos--] = DIGITS[Math.abs((int) (i % RADIX))];
        i /= RADIX;
    }
    return new String(buf, charPos + 1, (12 - charPos));
}

但是，尽管使用了Math.abs()，它仍然不能正确处理负值。

一旦这个问题解决了，我需要反向转换，但我希望这会更容易。您可以在您的答案中提供相关信息。

[编辑] 实际上，我刚刚查看了Long.parseLong(String s, int radix)的代码，看起来比Long.toString(long i, int radix)更加复杂。

5个回答
8
    long l = 0xffffffffffffffffL; // any long, e.g. -1

    // to string
    BigInteger bi = new BigInteger(Long.toString(l & ~(1L << 63)));
    if (l < 0) bi = bi.setBit(64);
    final String b36 = bi.toString(36);
    System.out.println("original long:" + l);
    System.out.println("result 36: " + b36);

    // parse
    final BigInteger parsedBi = new BigInteger(b36, 36);

    l = parsedBi.longValue();
    if (parsedBi.testBit(64)) l = l | (1L << 63);
    System.out.println("parsed long = " + l);

基准测试（一百万次操作）:
    // toString
    long l = 0x0ffffffffffffeffL;
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) toStringBi(l);
        System.out.println("BigInteger time = " + 
            (System.currentTimeMillis() - start) + " ms.");
    }
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) Long.toString(l, 36);
        System.out.println("Long.toString time = " + 
           (System.currentTimeMillis() - start) + "ms.");
    }
    // Parsing
    final String b36 = toStringBi(l);
    final String long36 = Long.toString(l, 36);
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            final BigInteger parsedBi = new BigInteger(b36, 36);
            l = parsedBi.longValue();
            if (parsedBi.testBit(64)) l = l | (1L << 63);
        }
        System.out.println("BigInteger.parse time = " 
            + (System.currentTimeMillis() - start) + " ms.");
    }
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) Long.parseLong(long36, 36);
        System.out.println("Long.parseLong time = " 
            + (System.currentTimeMillis() - start) + "ms.");
    }
  • BigInteger时间 = 1027毫秒。
  • Long.toString时间 = 244毫秒。
  • BigInteger.parse时间 = 297毫秒。
  • Long.parseLong时间 = 132毫秒。
好的。你得到了加一分，因为我可以使用它来测试另一个实现，但是我不会接受它，因为我已经明确表示解决方案不应使用BigInteger。 - Sebastien Diot
3
我刚做了一个基准测试 - 它比较慢，但大约可以在一秒钟内执行一百万次转换（仅比 Long.toString 慢四倍）。如果你想杀时间进行微观优化... 嗯，我认为这没必要。在这种情况下使用 BigInteger 就可以了。 - Eugene Retunsky
这些结果令人惊讶，我必须说。我之前提到的“非常慢”的评论是指我之前基准测试过的某些其他 BigInteger 的用法。我原本想在这个问题上设置赏金，但如果已经有答案的话就不可能了。我只能自己解决它。 :/ - Sebastien Diot
1
我的经历与此不同。我曾经有一个有关Scala的问题未被回答至少一个月。然后某个第三方为我的问题设置了赏金（我不知道这是可能的），大约两天后就得到了答案。在这里，人们确实会将赏金视为解决难题的“报酬”。 - Sebastien Diot
赏金只是帮助问题获得关注。这里人们真正接受的赏金是从解决难题中获得的满足感。记住，有人愿意为带有填字游戏的小书付费。而Stackoverflow则免费提供挑战 :) - Stijn de Witt
显示剩余2条评论
2

另一种选择是使用Google guava-libraries中的UnsignedLongs（其中还有许多其他好东西）：

String s = UnsignedLongs.toString( -1L, Character.MAX_RADIX );

并且

long l = UnsignedLongs.parseUnsignedLong( "2jsu3j", 36 );

从+EugeneRetunsky添加到基准测试中（见下文），这是在我的机器上得出的以下时间：

  • BigInteger时间（第一次运行）= 1306毫秒。
  • BigInteger时间（第二次运行）= 1075毫秒。
  • Long.toString时间 = 422毫秒。
  • UnsignedLongs.toString时间 = 445毫秒。
  • BigInteger.parse时间 = 298毫秒。
  • Long.parseLong时间 = 164毫秒。
  • UnsignedLongs.parseUnsignedLong时间 = 107毫秒。

出于好奇心，我让第一个测试运行两次以检查是否会改善时间。它始终如此（在我的机器上约为400毫秒），对于UnsignedLongs的情况也是如此。其他选项似乎不再从热点编译器中受益。

public class UnsignedLongsTest {
private static String toStringBi( long l ) {
    BigInteger bi = new BigInteger(Long.toString(l & ~(1L << 63)));
    if (l < 0) {
        bi = bi.setBit(64);
    }
    final String b36 = bi.toString(36);
    return b36;
}

public static void main( String[] args ) {
    // toString
    long l = 0x0ffffffffffffeffL;
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            toStringBi(l);
        }
        System.out.println("BigInteger time (1st run) = " +
                (System.currentTimeMillis() - start) + " ms.");
    }
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            toStringBi(l);
        }
        System.out.println("BigInteger time (2nd run) = " +
                (System.currentTimeMillis() - start) + " ms.");
    }
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            Long.toString(l, 36);
        }
        System.out.println("Long.toString time = " +
           (System.currentTimeMillis() - start) + "ms.");
    }
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            UnsignedLongs.toString(l, 36);
        }
        System.out.println("UnsignedLongs.toString time = " +
                (System.currentTimeMillis() - start) + "ms.");
    }
    // Parsing
    final String b36 = toStringBi(l);
    final String long36 = Long.toString(l, 36);
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            final BigInteger parsedBi = new BigInteger(b36, 36);
            l = parsedBi.longValue();
            if (parsedBi.testBit(64)) {
                l = l | (1L << 63);
            }
        }
        System.out.println("BigInteger.parse time = "
            + (System.currentTimeMillis() - start) + " ms.");
    }
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            Long.parseLong(long36, 36);
        }
        System.out.println("Long.parseLong time = "
            + (System.currentTimeMillis() - start) + "ms.");
    }
    {
        final long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            UnsignedLongs.parseUnsignedLong( long36, 36 );
        }
        System.out.println("UnsignedLongs.parseUnsignedLong time = "
                + (System.currentTimeMillis() - start) + "ms.");
    }
}
1
这看起来不快，但它是一个通用的解决方案，这是一件好事。我实际上正在考虑转移到Base-40，因为你可以使用Base-40对相同数量的字符（12个）进行编码，而你以前只能使用Base-36。 - Sebastien Diot
有趣。您在36以上使用哪四个字符？大写还是标点符号？我个人非常喜欢Base-36的大小写不敏感性。它在URL中很好用。 - mckamey
我“不使用URL”……我打算使用标点符号，因为我想将其用于用户名。添加下划线（代替空格）、破折号、句点和撇号有助于使登录名更易读。此外，覆盖更大范围的值有助于提高哈希效率。我想对所有我的ID使用长整型；我已经在我的DB API中硬编码了长整型作为表键类型（表值是byte[]）。 - Sebastien Diot
那么你的系统用户将拥有类似于z-ufh_w'.posg的随机用户ID，以对应其长密钥？ - mckamey
不！：D 我想让他们选择自己的登录ID，比如“whack-a-mole”，“jack_o'neill”或“j.smith”，然后将其转换为一个长密钥。 - Sebastien Diot
这可能是一个有限的搜索空间。例如，“sebastien.diot”将不被允许，因为它太长了。 - mckamey
1

尽管您表示“不接受任何涉及BigInteger的答案”，但您接受了一个BigInteger解决方案，这里提供另一种BigInteger解决方案。与其屏蔽符号，不如强制符号始终为正：

long input = 0xffffffffffffffffL; // any long, e.g. -1
byte[] bytes = ByteBuffer.allocate(8).putLong(input).array();

String base36 = new BigInteger(1, bytes).toString(36);
正如@tc所指出的那样，我的最终解决方案是首先检查符号，并尽可能使用Long。这为我的要求提供了足够的速度。 - Sebastien Diot
顺便提一下，当我尝试使用掩码解决方案时，它在往返解码时失败了。我不记得是哪个值导致的。 - mckamey
1
问题在于你正在寻找一个快速的无符号64位divmod，但只有一个有符号64位divmod。搜索udivmoddi3应该会给你一些C语言实现——这些通常用于在仅支持32位divmod硬件的体系结构上执行64位divmod。
请注意，你只需要抓住底部数字——一旦你做到了这一点，商将是正数，你可以使用Long.toString()。
如果基数是偶数（你说的是36进制），你可以轻松地获取底部数字（我的数学可能有误）：
int bottomDigit = ((value>>>1)%(radix/2))<<1)|((int)value&1);
long rest = (value>>>1)/(radix/2);
if (rest == 0)
{
  return Integer.toString(bottomDigit,radix);
}
return Long.toString(rest,radix) + Integer.toString(bottomDigit,radix);

一个明显的进一步优化是，如果值为正，则直接调用Long.toString()。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接