1

32 ビットおよび 64 ビット整数の最上位ビットを識別するための多くの優れたアルゴリズムを読みました (SO に関する他の投稿を含む)。しかし、私は BigIntegers を使用しており、最大 4000 ビット長の数値を処理します。(BigInteger は、4 のフラクタル深度で 1000 次元のハイパーキューブを蛇行するヒルベルト空間充填曲線にヒルベルト インデックスを保持します。)一般的なケースに最適でありながら、極端なケースにも対応できるソリューションが必要です。

素朴な方法は次のとおりです。

BigInteger n = 234762348763498247634; 
int count = 0; 
while (n > 0) {
    n >>= 1;
    count++;
}

私は、一般的なケースを Long に変換し、それらに 64 ビット アルゴリズムを使用することを考えていました。それ以外の場合は、非常に大きな数には別のアルゴリズムを使用します。しかし、Long への変換にどれだけコストがかかるか、また、64 ビット量で残りの計算を行う効率が低下するかどうかはわかりません。何かご意見は？

この関数の使用目的の 1 つは、逆グレイ コード計算の最適化を支援することです。

アップデート。2 つのアプローチをコーディングし、ベンチマークを実行しました。

  • 数値が Ulong.MaxValue 未満の場合、Ulong に変換して二分探索法を実行すると、BigInteger.Log を使用した場合の 2 倍の速さでした。

  • 数値が非常に大きい場合 (私は 10000 ビットまで上げました)、Log は 3.5 倍高速でした。

    MostSignificantBitUsingLog (Long に変換可能) への 100 万回の呼び出しで 96 ミリ秒が経過しました。

    MostSignificantBitUsingBinarySearch (Long に変換可能) への 100 万回の呼び出しで 42 ミリ秒が経過しました。

    MostSignificantBitUsingLog への 10,000 回の呼び出しで 74 ミリ秒が経過しました (大きすぎて変換できません)。

    MostSignificantBitUsingBinarySearch への 10,000 回の呼び出しで 267 ミリ秒が経過しました (大きすぎて変換できません)。

ログを使用するためのコードは次のとおりです。

public static int MostSignificantBitUsingLog(BigInteger i)
{
    int bit;
    if (i == 0)
        bit = -1;
    else
        bit = (int)BigInteger.Log(i, 2.0);

    return bit;
}

これが私の二分探索へのアプローチです。バイナリ除算を BigInteger 範囲に拡張するように改善できます。次に試してみます。

public static int MostSignificantBitUsingBinarySearch(BigInteger i)
{
    int bit;
    if (i.IsZero)
        bit = -1;
    else if (i < ulong.MaxValue)
    {
        ulong y = (ulong)i;
        ulong s;
        bit = 0;
        s = y >> 32;
        if (s != 0)
        {
            bit = 32;
            y = s;
        }
        s = y >> 16;
        if (s != 0)
        {
            bit += 16;
            y = s;
        }
        s = y >> 8;
        if (s != 0)
        {
            bit += 8;
            y = s;
        }
        s = y >> 4;
        if (s != 0)
        {
            bit += 4;
            y = s;
        }
        s = y >> 2;
        if (s != 0)
        {
            bit += 2;
            y = s;
        }
        s = y >> 1;
        if (s != 0)
            bit++;
    }
    else
        return 64 + MostSignificantBitUsingBinarySearch(i >> 64);

    return bit;
}

更新 2: バイナリ検索アルゴリズムを変更して、最大 100 万の 2 進数で BigInteger に対して機能し、64 ビット チャンクで再帰的に呼び出さないようにしました。ずっといい。テストの実行に 18 ミリ秒かかり、Log を呼び出すよりも 4 倍高速です。(以下のコードでは、MSB はループが展開された同じ種類のことを行う ulong 関数です。)

public static int MostSignificantBitUsingBinarySearch(BigInteger i)
{
    int bit;
    if (i.IsZero)
        bit = -1;
    else if (i < ulong.MaxValue)
        bit = MSB((ulong)i);
    else
    {
        bit = 0;
        int shift = 1 << 20; // Accommodate up to One million bits.
        BigInteger remainder;     
        while (shift > 0)
        {
            remainder = i >> shift;
            if (remainder != 0)
            {
                bit += shift;
                i = remainder;
            }
            shift >>= 1;
        }
    }
    return bit;
}
4

5 に答える 5

5

必要なビット数を表す log2 を計算できます。

var numBits = (int)Math.Ceil(bigInt.Log(2));
于 2012-04-04T13:24:20.223 に答える
2

二分探索問題のように扱うことができます。

上限は 4000 です (余裕を追加してください)

int m = (lo + hi) / 2;
BigInteger x = BigInteger(1) << m;

if (x > n) ...
else  ...
于 2012-04-04T13:26:38.257 に答える
0

C# ではなく Java を使用できる場合は、http://uzaygezen.googlecode.comで見つけることができる任意精度のヒルベルト曲線のインデックス作成用のライブラリがあります。グレイ コード インバースの実装については、前述のプロジェクトの LongArrayBitVector.grayCodeInverse または BitSetBackedVector.grayCodeInverse を詳しく調べてください。

于 2012-05-18T20:48:22.803 に答える