3

[編集] BigInteger、または他の同様の非効率的な方法を含む回答は受け付けていません。答える前に実際に質問を読んでください！

Java は、厄介なことに、符号なしの数値型をサポートしていません。次の例のように、次に大きな型を使用して、byte、short、または int を unsigned に変換できます。

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

しかし、より大きな型がないため、これを long で行うことはできません。

では、signed long を「unsigned」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);

ベンチマーク (100 万回の操作):

    // 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 時間 = 132ms。
于 2012-03-28T18:52:33.943 に答える
2

もう 1 つのオプションは、 Google の guava-librariesからUnsignedLongsを使用することです (他にも多くの機能があります)。

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

と

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

+EugeneRetunsky (以下を参照) からのベンチマークに追加すると、私のマシンで次の時間が得られます。

  • BigInteger 時間 (1 回目の実行) = 1306 ミリ秒。
  • BigInteger 時間 (2 回目の実行) = 1075 ミリ秒。
  • Long.toString 時間 = 422ms。
  • UnsignedLongs.toString 時間 = 445 ミリ秒。
  • BigInteger.parse 時間 = 298 ミリ秒。
  • Long.parseLong 時間 = 164ms。
  • UnsignedLongs.parseUnsignedLong 時間 = 107ms。

好奇心から、最初のテストを 2 回実行して、時間が改善されるかどうかを確認しました。UnsignedLongsの場合でも、一貫して（私のマシンでは〜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.");
    }
}
于 2013-12-12T15:08:05.070 に答える
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 に答える
1

また、バイト配列として long を使用している場合、@JonnyDee には、バイト配列が Base-256 の数値であると見なす場合に適用できる任意の 2 つの基数間で変換するためのアルゴリズム (Python では短い) があります。数字。バイトに戻す変換は、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

「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 に答える