3

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

令人讨厌的是，Java 不支持无符号数字类型。您可以使用下一个更大的类型将字节、short 或 int 转换为无符号，例如：

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

但是你不能用 long 来做这个，因为没有更大的类型。

那么，如何将有符号的 long 转换为“无符号”base-X，在我的情况下为 base-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)更复杂。

4

5 回答 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 毫秒。
于 2012-03-28T18:52:33.943 回答
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.");
    }
}
于 2013-12-12T15:08:05.070 回答
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);
于 2012-07-24T17:48:31.467 回答
1

此外，如果您使用 long as 字节数组，@JonnyDee 有一个算法（在 Python 中，但它很短）用于在任何两个基数之间进行转换，如果您认为字节数组是 Base-256 的数字，则适用于此处位数。转换回字节只是将 base-36 转换为 base-256。

https://stackoverflow.com/a/6158278/43217

以及他相应的博文：

https://jonnydee.wordpress.com/2011/05/01/convert-a-block-of-digits-from-base-x-to-base-y/

于 2012-07-24T17:53:07.517 回答
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()一个明显的进一步优化是如果值为正则直接调用。

于 2012-07-24T18:13:17.323 回答