3

正の整数をテストして、バイナリ表現が 0 個以上の 1 で始まり、その後に 1 個以上の 0 が続くかどうかを確認したいと考えています。

00000000 // Valid
10000000 // Valid
11000000 // Valid
11100000 // Valid
11110000 // Valid
11111100 // Valid
11111110 // Valid
11111110 // Valid
11111111 // Not Valid
// Any other combination is Not Valid

同じものを正規表現で表現すると、^[1]*[0]+$ になります。もちろん、これは説明のためだけのものであり、正規表現は使用できません。

ブルートフォースは次のようにアプローチします。

  • 複数のビット マスクを作成し、AND を組み合わせて結果を決定します。
  • 動的マスクを使用して各桁をループし、結果を決定します。

問題は、数十万桁の巨大な正の整数を扱っており、そのような数千の数に対してこのテストを実行する必要があることです。

このバイナリ パターンを決定するより効率的な方法はありますか?

アップデート

これが私が試した実装です。まだ他の回答と時間を比較していません。

public static bool IsDiagonalToPowerOfTwo (this System.Numerics.BigInteger number)
{
    byte [] bytes = null;
    bool moreOnesPossible = true;

    if (number == 0) // 00000000
    {
        return (true); // All bits are zero.
    }
    else
    {
        bytes = number.ToByteArray();

        if ((bytes [bytes.Length - 1] & 1) == 1)
        {
            return (false);
        }
        else
        {
            for (byte b=0; b < bytes.Length; b++)
            {
                if (moreOnesPossible)
                {
                    if (bytes [b] == 255)
                    {
                        // Continue.
                    }
                    else if
                    (
                        ((bytes [b] & 128) == 128) // 10000000
                        || ((bytes [b] & 192) == 192) // 11000000
                        || ((bytes [b] & 224) == 224) // 11100000
                        || ((bytes [b] & 240) == 240) // 11110000
                        || ((bytes [b] & 248) == 248) // 11111000
                        || ((bytes [b] & 252) == 252) // 11111100
                        || ((bytes [b] & 254) == 254) // 11111110
                    )
                    {
                        moreOnesPossible = false;
                    }
                    else
                    {
                        return (false);
                    }
                }
                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
    }

    return (true);
}
4

3 に答える 3

3

整数がバイナリで格納され、符号なし整数の配列 x[] にグループ化されていると仮定すると、これを実行できます。

Define UINT to be the unsigned integer type you are using for the grouped bits.
Define UMAX to be the maximum value of that type (all bits are on).

// Find first word that has a zero bit.
int i;
for (i = highest word in x; 0 <= i; --i)
    if (x[i] != UMAX)
        break;

// Return true if all bits in all of x[] are on.
if (i < 0)
    return true;

// Test whether word conforms to the ones-then-zeroes rule.
UINT y = x[i];
if (y + (y & -y))
    return false;

// Test whether all remaining words are zero.
for (; 0 <= i; --i)
    if (x[i])
        return false;

return true;

ではy + (y & -y)、y & -yy に設定された最下位ビットを返します。(読者のための演習として残されている証明。) y のすべての上位ビットがオンの場合、その最下位ビットを追加すると、それらすべてのビットにキャリーが伝搬され、それらがゼロに変更されます。これらの上位ビットのいずれかがオフの場合、キャリーは停止し、結果はゼロではありません。それ以外の場合、結果はゼロです。

上記を改善できますか？比較と分岐は、AND などの演算よりもコストが高いとします。その場合、バイナリ検索を使用して、配列内で値がすべて 1 からすべて 0 に変化する場所、またはどちらにも変化しない場所を見つけることができます。上記のように特定された重要な単語をテストし、次にすべての高い値を AND して、その結果をすべて 1 についてテストし、次にすべての低い値を OR して、その結果をすべて 0 についてテストします。

これにより、バイナリ検索が行われ、その後に 1 つのロードと、単語ごとに 1 つの AND または OR が続きます。そこを改善するのは難しいでしょう。

于 2012-08-05T18:01:40.800 に答える
1

最悪の場合、入力に関する追加データが保存されていないと、数値のすべてのビットを調べる必要があるため、O（ n）アルゴリズム（ nはビット数）よりも優れた方法はありません。

以前の操作で「右端の1」や「左端の0」などを追跡できれば、これらが本当に「10」であるかどうかを確認することで、すぐに答えを得ることができます。

それ以外の場合は、ビットを効果的に反復して、それが正しいかどうかを確認する必要があります。1に達するまで左から数字を調べ、すべてが0であるかどうかをチェックする（適切なコーナーケースを使用する）のはO（n）であるのに対し、O（n）の可能な値の完全なリストがあり、 （おそらく？）O（n）の比較でそれらのいずれかに等しいO（n ^ 2）であるため、悪い考えです。

于 2012-08-05T16:05:08.197 に答える
0

バイナリデータを固定サイズのブロックに分割します... 32ビット... 64ビット->それらを符号なし整数として扱います

すべての有効なパターンと逆パターン (「0」で始まり「1」で終わる) を含む 2 つのハッシュマップを準備します ... ここでも符号なし整数です

左端のブロックが逆パターン ハッシュマップに含まれているかどうかをテストします ... そうでない場合 -> パターンが無効です
今、右端 (ゼロ以外) のブロックが通常のパターン ハッシュマップに含まれているかどうかをテストします ... そうでない場合 ->パターンが無効です

ここで、他のすべてのブロックが全ビット セット パターンと等しいかどうかをテストします (これは、符号なし整数との比較である必要があります) ... すべてが等しい場合 -> パターンは有効です ... そうでなければ ... パターンは無効です

于 2012-08-05T16:14:01.967 に答える