Как вы конвертируете длинный Java в *unsigned* base-X String (и обратно)?
[РЕДАКТИРОВАТЬ] Я НЕ принимаю никакого ответа, который включает BigInteger, или другой столь же неэффективный метод. Пожалуйста, прочитайте вопрос, прежде чем ответить!
К сожалению, Java не поддерживает типы чисел без знака. Вы можете преобразовать byte, 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).
5 ответов
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.
Другой вариант - использовать UnsignedLongs из guava-библиотек Google (которые также имеют много других полезностей):
String s = UnsignedLongs.toString( -1L, Character.MAX_RADIX );
а также
long l = UnsignedLongs.parseUnsignedLong( "2jsu3j", 36 );
Добавленный к тесту от +EugeneRetunsky (см. Ниже), это дает следующие времена на моей машине:
- Время BigInteger (1-й прогон) = 1306 мс.
- Время BigInteger (второй прогон) = 1075 мс.
- Long.toString time = 422 мс.
- UnsignedLongs.toString time = 445мс.
- BigInteger.parse время = 298 мс.
- Long.parseLong time = 164 мс.
- UnsignedLongs.parseUnsignedLong time = 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.");
}
}
Проблема в том, что вы ищете быстрый беззнаковый 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() напрямую, если значение положительное.
Поскольку, несмотря на то, что "НЕ принимаем никаких ответов, связанных с 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);
Кроме того, если вы работаете с длинным байтовым массивом, @JonnyDee имеет алгоритм (в Python, но он короткий) для преобразования между любыми двумя базами, который применим здесь, если вы считаете, что байтовый массив является числом с Base-256 цифры. Преобразование обратно в байты - это просто преобразование base-36 в base-256.
/questions/25580761/raspechatat-bolshoj-massiv-256-v-baze-10-v-s/25580775#25580775
И его соответствующий пост в блоге:
https://jonnydee.wordpress.com/2011/05/01/convert-a-block-of-digits-from-base-x-to-base-y/