3

2 つの 1 ビットだけが残るまで、指定された BigInteger のすべての下位ビットを 0 に設定する必要があります。つまり、最上位ビットと 2 番目に上位のビットを設定したままにし、他のすべてのビットを設定解除します。

数値は、任意のビットの組み合わせにすることができます。すべて 1 またはすべて 0 の場合もあります。例：

MSB    0000 0000
       1101 1010
       0010 0111
       ...
       ...
       ...
LSB    0100 1010

0、1、PowerOf2 などのコーナー ケースを簡単に取り除くことができます。1 つの数値を表すバイト配列に一般的なビット操作アルゴリズムを適用する方法がわかりません。

私はすでにビットハックを見てきましたが、次の制約があります。BigInteger 構造体は、それ自体が高価で不要な ToByteArray メソッドを介して基礎となるデータのみを公開します。これを回避する方法がないため、32/64 ビット整数 (ほとんどの場合) に最適化されたビット カウント アルゴリズムを実装することで、これ以上速度を落としたくありません。

要するに、任意の大きな数を表すバイト [] があります。ここでは速度が重要な要素です。

注：参考までに、私が扱っている数値は約5,000,000ビットです。それらはアルゴリズムの反復ごとに減少し続けるため、数値の大きさが減少するにつれて、おそらく手法を切り替えることができます.

なぜこれを行う必要があるのか​​:私は 2D グラフを扱っており、x と y の値が 2 の累乗である座標に特に関心があります。したがって、(x+y) には常に 2 つのビットが設定され、(xy) には常に連続したビットが設定されます。ビットセット。任意の座標 (x, y) が与えられた場合、最初の 2 つの MSB を除くすべてのビットが設定されていない値を取得して、交点を変換する必要があります。

4

2 に答える 2

2

次のことを試してください (実際に有効な C# かどうかはわかりませんが、十分に近いはずです)。

// find the next non-zero byte (I'm assuming little endian) or return -1
int find_next_byte(byte[] data, int i) {
    while (data[i] == 0) --i;
    return i;
}

// find a bit mask of the next non-zero bit or return 0
int find_next_bit(int value, int b) {
    while (b > 0 && ((value & b) == 0)) b >>= 1;
    return b;
}

byte[] data;

int i = find_next_byte(data, data.Length - 1);
// find the first 1 bit
int b = find_next_bit(data[i], 1 << 7);
// try to find the second 1 bit
b = find_next_bit(data[i], b >> 1);
if (b > 0) {
    // found 2 bits, removing the rest
    if (b > 1) data[i] &= ~(b - 1);
} else {
    // we only found 1 bit, find the next non-zero byte
    i = find_next_byte(data, i - 1);
    b = find_next_bit(data[i], 1 << 7);
    if (b > 1) data[i] &= ~(b - 1);
}

// remove the rest (a memcpy would be even better here,
// but that would probably require unmanaged code)
for (--i; i >= 0; --i) data[i] = 0;

未テスト。

おそらく、アンマネージ コードとしてコンパイルしたり、C または C++ コンパイラを使用してコンパイルしたりすると、パフォーマンスが少し向上します。

harold が正しく指摘したように、自分の番号についてアプリオリな知識がない場合は、このO(n)方法が最善の方法です。可能であれば、ゼロ以外の上位 2 バイトの位置を保持する必要があります。これにより、変換の実行に必要な時間が大幅に短縮されます。

于 2012-08-19T21:25:27.670 に答える
1

これが最適化されているかどうかはわかりませんが、このコードはToByteArrayより16倍高速であるように見えます。また、メモリコピーを回避し、バイトではなくuintとして結果を取得することを意味するため、そこでさらに改善する必要があります。

//create delegate to get private _bit field
var par = Expression.Parameter(typeof(BigInteger));
var bits = Expression.Field(par, "_bits");
var lambda = Expression.Lambda(bits, par);
var func = (Func<BigInteger, uint[]>)lambda.Compile();

//test call our delegate
var bigint = BigInteger.Parse("3498574578238348969856895698745697868975687978");
int time = Environment.TickCount;
for (int y = 0; y < 10000000; y++)
{
    var x = func(bigint);
}
Console.WriteLine(Environment.TickCount - time);

//compare time to ToByteArray
time = Environment.TickCount;
for (int y = 0; y < 10000000; y++)
{
    var x = bigint.ToByteArray();
}
Console.WriteLine(Environment.TickCount - time);

そこから上位2ビットを見つけるのは非常に簡単です。最初のビットは私が推測する最初のintにあり、それから2番目に上位のビットを検索するだけです。同じ整数の場合は、最初のビットをゼロに設定して最上位ビットを検索します。それ以外の場合は、次のゼロなしintを検索して、最上位ビットを検索します。

編集：物事を簡単にするには、このクラスをコピーしてプロジェクトに貼り付けるだけです。これにより、拡張メソッドが作成されます。つまり、mybigint.GetUnderlyingBitsArray（）を呼び出すだけです。サインを取得するメソッドも追加し、より一般的にするために、任意のオブジェクトの任意のプライベートフィールドにアクセスできるようにする関数を作成しました。これは、デバッグモードでは元のコードよりも低速ですが、リリースモードでは同じ速度であることがわかりました。これを自分でパフォーマンステストすることをお勧めします。

static class BigIntegerEx
{
    private static Func<BigInteger, uint[]> getUnderlyingBitsArray;
    private static Func<BigInteger, int> getUnderlyingSign;

    static BigIntegerEx()
    {
        getUnderlyingBitsArray = CompileFuncToGetPrivateField<BigInteger, uint[]>("_bits");
        getUnderlyingSign = CompileFuncToGetPrivateField<BigInteger, int>("_sign");
    }

    private static Func<TObject, TField> CompileFuncToGetPrivateField<TObject, TField>(string fieldName)
    {
        var par = Expression.Parameter(typeof(TObject));
        var field = Expression.Field(par, fieldName);
        var lambda = Expression.Lambda(field, par);
        return (Func<TObject, TField>)lambda.Compile();
    }

    public static uint[] GetUnderlyingBitsArray(this BigInteger source)
    {
        return getUnderlyingBitsArray(source);
    }

    public static int GetUnderlyingSign(this BigInteger source)
    {
        return getUnderlyingSign(source);
    }
}
于 2012-08-19T23:16:29.460 に答える