biginteger如何将Java long转换为*无符号*baseX字符串（以及返回）？

Question

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

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

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

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

那么，如何将有符号的long转换为“无符号”的base-X，在我的例子中是base-36，然后再转换回来？Long类具有这些方法，但将Long视为有符号的，因为它们是有符号的

我可能可以使用一些操作和BigInteger来实现这一点，但是BigInteger的速度非常慢，并且通过临时创建BigInteger来创建垃圾。我会做很多转换（我想）。我需要一个与Long的默认实现一样高效的算法。toString（长i，整数基数）

试图修改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));
}

但它不能正确处理负值，尽管有数学上的原因。abs（）

一旦这项工作，我需要反向转换，但我希望它会更容易。欢迎你也把它写进你的答案里

[编辑]实际上，我只是看了很久代码。parseLong（字符串s，int基数），它看起来比Long更复杂。toString（长i，整数基数）

Answer 1

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

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

及

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

添加到+EugeneRetunsky（见下文）的基准测试中，这将在我的机器上提供以下时间：

• BigInteger时间（第一次运行）=1306毫秒
• BigInteger时间（第二次运行）=1075毫秒
• 长。toString时间=422ms
• 未签名的。toString时间=445ms
• 大整数。解析时间=298毫秒
• 长。解析长时间=164ms
• 未签名的。parseUnsignedLong时间=107ms

出于好奇，我让第一个测试运行了两次，以检查这是否会缩短时间。它始终如此（在我的机器上约400ms），也适用于未签名的情况。其他选项似乎不再从热点编译器中获益

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.");
    }
}

Answer 2

    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毫秒
• 长。toString时间=244ms
• 大整数。解析时间=297毫秒
• 长。解析长时间=132ms

Answer 3

此外，如果你使用的是一个字节数组，@ 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/

Answer 4

尽管“不接受任何涉及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);

Answer 5

问题是，您正在寻找一个快速的无符号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()