6

これはおそらく十分にカバーされた地面ですが、私はこの件について無知なので、素人っぽい用語を使用します. それぞれがint内のゼロ以外の数値セットを定義するいくつかの条件セットをいじっているとしましょう.8ビットintとしましょう。したがって、ビット単位の場合、次のようになります。

11XX00XX

1 がある場所には 1、0 がある場所には 0 があり、X は気にしないすべてのバイトが必要だと言います。したがって、11110000 または 11000010 はこれを満たしますが、01110000 は満たしません。簡単ですよね？算術条件については、定数と比較して、==、!=、>=、>、<=、または < が使用されていることしか想像できません。だから私は言うかもしれません：

X > 16

つまり、16 (00010000) より大きい任意の数です。上記の例セットの両方に含まれるすべての数値を検索したい場合はどうすればよいでしょうか? これを見ると、100XX で終わる数値はすべて要件に適合することがわかります。したがって、交差部分のビット単位の部分には 11X100XX が含まれます。次に、領域 111X00XX を含めて、その上の残りの範囲も埋める必要があります。右？他の場合だと思いますが、綺麗にはなりませんよね？とにかく、この背後にあるアルゴリズムは何ですか?これらの算術条件と、可能なビット単位の条件のいずれかです。確かに一般的な場合があるに違いありません！

1 つあると仮定すると、それはおそらく明白なものですが、事態がさら​​に複雑になるとどうなるでしょうか? ビットごとの要件が次のようになったらどうなりますか。

11AA00XX

A でマークされているものはすべて同じでなければなりません。つまり、110000XX または 111100XX ですが、111000XX ではありません。任意の数の任意の位置にある同じビット「タイプ」(A、B、C など) について、算術比較を使用して交差を解決する最適な方法は何ですか? ありますか？

これらのビット単位の操作は、算術演算がどのようにセットアップされるかと同じように、一種の単一の比較操作/分岐であると考えています。したがって、おそらく 1 つは、バイト B 01110000 がそれらと AND されると、00110000 になるすべての定数です。したがって、私の「ビット単位の条件」である定数の領域は、X011XXXX AND 01110000 = 00110000 であるため、X011XXXX になります。 . 私の「ビットごとの条件」はすべて、AND、OR、XOR などの演算の反転によって形成されます。NANDのようなものが含まれるかどうかはわかりません。これにより、実際に可能な条件が制限される可能性があります。もしそうなら、私はそれらの種類の条件を気にしません。

蛇行した説明で申し訳ありません。私がしていることに名前はありますか？それはCSで十分に踏襲されているように思われるので、名前があれば、このテーマに関するいくつかの素晴らしい読み物につながる可能性があります. しかし、私は主にこれを解決するための優れたアルゴリズムを探しています。交差点で 2 つ以上のもの (潜在的に数十またはそれ以上) を使用することになるので、適切にスケーリングして解決する方法は大きなプラスになります。

4

5 に答える 5

7

ビット単位

さて、ビット単位の演算を見てみましょう。これが、必要なことを実行するための最も効率的な方法です。わかりやすくするため（および参照用）、10進数に変換されたビット単位の値は次のとおりです。

00000001 =   1
00000010 =   2
00000100 =   4
00001000 =   8
00010000 =  16
00100000 =  32
01000000 =  64
10000000 = 128

11XX00XXここで、変数のビットパターンが与えられた場合x、次のチェックを実行します。

x AND 128 == true
x AND 64  == true
x AND 8   == false
x AND 4   == false

これらの条件がすべて当てはまる場合、値はパターンに一致します。基本的に、次の条件をチェックしています。

1XXXXXXX AND 10000000 == true
X1XXXXXX AND 01000000 == true
XXXX0XXX AND 00001000 == false
XXXXX0XX AND 00000100 == false

それをプログラミング言語の用語でまとめると（私はC＃を使用します）、次のように検索します。

if ((x && 128) && (x && 64) && !(x && 8) && !(x && 4))  
{
    // We have a match
}

11AA00XXのより複雑なビットパターンの場合、次の条件を追加します。

NOT ((x AND 32) XOR (x AND 16)) == true

これが行うことは、最初にチェックx AND 32し、のそのビットの値に基づいて0または1を返しますx。次に、他のビットで同じチェックを行いx AND 16ます。このXOR操作はビットの違いをチェックし、ビットが異なる場合は1を返し、ビットが同じ場合は0を返します。そこから、同じ場合は1を返したいので、NOT句全体を返します。ビットが同じ場合、これは1を返します。

算術的に

算術側では、除算とモジュラス演算の組み合わせを使用して、問題のビットを分離することを検討します。除算を使用するには、数値を除算できる2の可能な最大の累乗を見つけることから始めます。つまり、を持っている場合x=65、2の最大の累乗は64です。

除算が完了したら、モジュラスを使用して除算後の余りを取ります。上記の例のように、が与えられx=65ますx MOD 64 == 1。その数を使用して、前に行ったことを繰り返し、2の最大の累乗を見つけ、モジュラスが0を返すまで続けます。

于 2012-05-08T19:10:14.060 に答える
7

salice の答えを少し拡張します。

ビットテスト

テスト パターンを作成できるので、各ビットを個別にチェックする必要はありません (整数をテストする方が、1 ビットずつテストするよりも高速です。良い）：

testOnes = 128 & 64 // the bits we want to be 1
testZeros = ~(8 & 4) // the bits we want to be 0, inverted

次に、この方法でテストを実行します。

if (!(~(x & testOnes) & testOnes) &&
    !(~(~x | testZeros))) {
  /* match! */
}

ロジックの説明:

まず第一に、両方testOnesで、testZeros関心のあるビットを 1 に設定し、残りを 0 に設定します。

testOnes testZeros
11000000 11110011

次にx & testOnes、1 であるかどうかをテストしたくないすべてのビットをゼロにします ( と の違いに注意してください&:&&は&論理AND演算をビット単位で実行しますが、 は整数の論理演算です) &&。AND

testOnes
11000000
x        x & testOnes
11110000 11000000
11000010 11000000
01010100 01000000

現在、1 であるかどうかをテストしているビットはせいぜい 1 である可能性がありますが、それらすべてが 1 であるかどうかはわかりません。結果 ( ~(x & testOnes)) を反転すると、1 であることを気にしないすべての数値とテストしたいのは、0 (1 の場合) または 1 (0 の場合) です。

testOnes
11000000
x        ~(x & testOnes)
11110000 00111111
11000010 00111111
01010100 10111111

ANDそれをビット単位で処理することによりtestOnes、関心のあるビットがすべて 1 の場合は 0 になりx、それ以外の場合は非ゼロになります。

testOnes
11000000
x        ~(x & testOnes) & testOnes
11110000 00000000
11000010 00000000
01010100 10000000

この時点で、1 をテストしたいすべてのビットが実際に 1 の場合は 0 であり、それ以外の場合は非 0 であるため、論理演算を実行しNOTて 0 をtrueに、非 0 を に変換しfalseます。

x        !(~(x & testOnes) & testOnes)
11110000 true
11000010 true
01010100 false

ゼロビットのテストも同様ですが、bitwise- ( ) の代わりに bitwise- ( ) を使用する必要ORが|ありANDます&。まず、 を反転xして、0 であるべきビットORを 1 にする必要があります。したがって、この時点で、0 であるべきビットxが実際に 0 の場合はすべて 1 であり、そうでない場合はすべて 1 ではないため、結果を再度反転して、最初のケースで 0 を取得し、2 番目のケースで非 0 を取得します。 . 次に、論理NOT( ) を適用して、結果を(最初のケース) または(2 番目のケース)!に変換します。truefalse

testZeros
11110011
x        ~x       ~x | testZeros ~(~x | testZeros) !(~(~x | testZeros))
11110000 00001111 11111111       00000000          true
11000010 00111101 11111111       00000000          true
01010100 10101011 11111011       00000100          false

注: 各テストで 4 つの操作を実行したため、合計で 8 つの操作を実行したことを認識する必要があります。テストするビット数によっては、これでも各ビットを個別にチェックするよりも少ない場合があります。

算術テスト

等しいかどうかのテストは簡単です:XORテストされた数値 -- すべてのビットが等しい (したがって数値が等しい) 場合は 0 を取得し、少なくとも 1 つのビットが異なる (したがって数値が異なる) 場合は 0 以外を取得します。（適用するNOTと、同等のテスト結果trueが 、差が になりfalseます。）

ただし、不等式をテストするには、少なくとも論理演算に適用される場合、ほとんどの場合運が悪くなります。2 の累乗 (例: 質問の 16) のチェックは論理演算 (ビットごとANDの 0 のテスト) で行うことができますが、2 の累乗ではない数値の場合、そうではありません。簡単。例として、 をテストしてみましょうx>5: パターンは 00000101 ですが、どのようにテストしますか? 最初の 5 つの最上位ビットに 1 がある場合、数値は大きくなりますが、最初の 5 ビットがすべて 0 である 6 (00000110) も大きくなります。

あなたができる最善のことは、数値が数値の最大の 2 の累乗の少なくとも 2 倍であるかどうかをテストすることです (上記の例では 5 に対して 4)。はいの場合、元のサイズよりも大きくなっています。それ以外の場合は、少なくとも 2 の累乗の最大値と同じである必要があり、下位ビットに対して同じテストを実行します。ご覧のとおり、操作の数は、テスト番号の 1 ビットの数に基づいて動的です。

リンクされたビット

これがあなたXORの友達です。2 つのビットXORが同じ場合は 0 になり、そうでない場合は 1 になります。

テストを実行する簡単な方法はわかりませんが、次のアルゴリズムが役立つはずです。

b1ビット, ...を同じ (すべて 1 またはすべて 0) にする必要があると仮定bnし、他のすべてのビットをゼロにして (AND上記の論理を参照)、テスト パターン内の各ビットを分離し、それらを次の位置に並べます。同じ位置 (便宜上、最下位ビットにしましょう)。次にXOR、それらのうちの 2 つをXOR-ing し、結果を 3 つ目に -ing すると、奇数ステップごとに偶数が生成され、元の数でビットが同じである場合は、偶数ステップごとに奇数が生成されます。最終結果のみをテストすると、テスト対象のリンクされたビットが多数になると正しくない可能性があるため、すべてのステップでテストする必要があります。

testLinks
00110000
x        x & testLinks
11110000 00110000
11000010 00000000
01010100 00010000

x        x's bits isolated isolated bits shifted
11110000 00100000          00000001
         00010000          00000001
11000010 00000000          00000000
         00000000          00000000
01010100 00000000          00000000
         00010000          00000001

x        x's bits XOR'd result
11110000 00000000       true (1st round, even result)
11000010 00000000       true (1st round, even result)
01010100 00000001       false (1st round, odd result)

注: C ライクな言語では、XOR演算子は^.

注: ビットを同じ位置に並べるには? ビットシフト。左シフト ( <<) は、すべてのビットを左にシフトし、最上位ビットを「失い」、最下位ビットに 0 を「導入」し、基本的に数値を 2 倍します。shift-right ( >>) も同様に動作し、ビットを右にシフトし、基本的に整数を 2 で除算しますが、同じビットを既に存在していた最上位ビットに「導入」します (したがって、負の数を負のままにします)。 .

于 2012-05-09T10:44:23.273 に答える
1

TLDRサルースの答え：

ビット単位のチェックでは個々のビットが個別に考慮され、算術チェックではすべてのビットがまとめて考慮されます。確かに、それらは 2 の累乗では一致しますが、任意の数では一致しません。

したがって、両方ある場合は、両方のチェック セットを実装する必要があります。

32 ビット int のすべての可能な値のスペースは、格納するには少し大きいため、毎回すべてをチェックする必要があります。x > 5 || のような重複チェックを排除するために、短絡を使用していることを確認してください。x > 3。

于 2012-05-09T11:13:18.423 に答える
1

マスクを指定するための適切な DSL を定義しました。そのマスクを読み取り、それぞれの固有の文字に固有の操作を実行するパーサーを作成します。

AABBB110 = マスク

ステップ 1: すべての一意の文字を配列 [01AB] に抽出します。操作は必要ないため、「X」は省略できます。

ステップ 2: その配列を反復処理し、テキスト マスクを個別のビット マスクに処理し、一意の文字ごとに 1 つずつ、その文字配置のビットを 1 に置き換え、その他すべてを 0 に置き換えます。

Mask_0 = 00000001 = 0x01
Mask_1 = 00000110 = 0x06
Mask_A = 11000000 = 0xC0
Mask_B = 00111000 = 0x38

ステップ 3: 以下に定義されているように、各マスクを適切な関数に渡します。

boolean mask_zero(byte data, byte mask) {
  return (data & mask) == 0;
}

boolean mask_one(byte data, byte mask) {
  return (data & mask) == mask;
}

boolean mask_same(byte data, byte mask) {
  byte masked=data & mask;
  return (masked==0) || (masked==mask);
}
于 2012-05-13T01:13:03.027 に答える
1

結果セットの形式を指定してください。算術セット (これを A と呼びましょう) とビット単位セット (これを B と呼びましょう) の両方に、迅速にテストできるという利点と、簡単に反復できるという利点の両方があります。しかし、これらの種類の定義のそれぞれは、他の定義では定義できないものを定義できるため、それらの共通点はまったく別のものである必要があります。

私がすることは、テストと反復を別々に処理することです。簡単にテスト可能な定義は、論理「and」を使用するだけで、両方のセットを任意の数式に変換することで簡単に作成できます (他のポスターが説明しているように、ビット単位のセットはいくつかのビット単位の操作に変換できます)。これは、あらゆる種類のセットに簡単に一般化できます。単純に両方の親セットへの参照を格納し、数値が両方のセットにあるかどうかを尋ねられたら、両方の親セットを確認するだけです。

ただし、任意の数式を繰り返し処理するのは簡単ではありません。反復の場合、最も簡単な方法は、セット B を反復し (セットによって制約されていないビットのみを変更することで実行できます)、セット A が結果を制約できるようにすることです。A が > または >= を使用する場合、(最大数から) 下方向に反復し、最大の効率を得るために false で停止します。A が < または <= を使用する場合、(最小数から) 反復し、false で停止します。A が == を使用する場合、チェックする数値は 1 つだけです。A が != を使用する場合、どちらの方向でも問題ありません (ただし、false で停止することはできません)。

ビット単位のセットは、数値のインデックス可能な配列のように動作できることに注意してください。たとえば、11XX00XX で定義されたビット単位のセットは、0000 から 1111 までの範囲のインデックスを持つ配列として扱うことができ、インデックスのビットは対応するスロットに収まります。これにより、セットを上下に反復することが容易になります。セット A は同様の方法でインデックス付けできますが、簡単に無限セットになる可能性があるため (マシンの int 値によって制約されない限り、つまり BigInteger である必要はありません)、反復するのが最も安全なことではありません。以上。

于 2012-05-13T15:07:20.587 に答える