Как вы конвертируете длинный Java в * unsigned * base-X String (и обратно)?

Question

[РЕДАКТИРОВАТЬ] Я НЕ принимаю никакого ответа, который включает BigInteger, или другой аналогичный неэффективный метод. Пожалуйста, на самом деле прочитайте вопрос, прежде чем ответить!

Java, достаточно досадно, не поддерживает типы чисел без знака. Вы можете преобразовать байт, short или int в unsigned, используя следующий больший тип, например:

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

Но вы не можете делать это долго, поскольку нет более крупного типа.

Итак, как вы конвертируете long со знаком в "unsigned" base-X, в моем случае base-36, и обратно? Класс 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 ().

Как только это сработает, мне нужно обратное преобразование, но я надеюсь, что это будет проще. Пожалуйста, добавьте это в свой ответ.

[EDIT] На самом деле, я только что посмотрел код Long.parseLong (String s, int radix), и он выглядит на более сложнее, чем Long.toString (long i, int radix).

Answer 1

    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 time = 244 мс.
• BigInteger.parse время = 297 мс.
• Long.parseLong time = 132ms.

Answer 2

Другой вариант - использовать UnsignedLongs из Google guava-библиотек (которые также имеют множество других вкусностей):

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

и

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

Добавлен в бенчмарк от + EugeneRetunsky (см. Ниже), это дает следующие времена на моей машине:

• Время BigInteger (1-й прогон) = 1306 мс.
• Время BigInteger (2-й прогон) = 1075 мсек.
• Long.toString time = 422 мс.
• UnsignedLongs.toString time = 445ms.
• BigInteger.parse время = 298 мс.
• Long.parseLong time = 164 мс.
• UnsignedLongs.parseUnsignedLong time = 107ms.

Из любопытства я позволил первому тесту пройти дважды, чтобы проверить, не улучшит ли это время. Это постоянно (до ~ 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.");
    }
}

Answer 3

Проблема в том, что вы ищете быстрый беззнаковый 64-битный divmod, имеющий только 64-битный divmod со знаком.Поиск udivmoddi3 должен дать вам несколько реализаций в C - они обычно используются для выполнения 64-битного divmod на архитектурах, которые поддерживают только 32-битный 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(), если значение положительное.

Answer 4

Кроме того, если вы работаете с длинным байтовым массивом, @JonnyDee имеет алгоритм (в Python, но он короткий) для преобразования между любыми двумя базами, который применим здесь, если вы считаете байтовый массив числом сБаза-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 5

Поскольку, несмотря на то, что «НЕ принимаем никаких ответов, связанных с 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);