4

数日前、私の先生は、ビット演算子だけを使用して、特定の点が特定の長方形の内側にあるかどうかを確認できると教えてくれました。それは本当ですか？もしそうなら、どうすればそれを行うことができますか？

4

3 に答える 3

3

これはあなたの質問に答えないかもしれませんが、あなたが探しているのはこれかもしれません。
これらはSeanEronAndersonによって編集されたトリックであり、彼は単一のバグを見つけることができる人のために10ドルの報奨金さえ与えました。ここで私が見つけた最も近いものは、整数XにMとNの間にある単語があるかどうかを見つけるマクロです。

単語のバイト数がmからnかどうかを判断します

m <nの場合、この手法は、単語xに符号なしバイト値が含まれているかどうかをテストします（m <値<n）。nとmが定数の場合、7つの算術/論理演算を使用します。注：nに等しいバイトは、誤検知として報告される可能性が高いため、特定の結果が必要な場合は、文字で確認する必要があります。

要件：x> = 0; 0 <= m <= 127; 0 <= n <= 128

#define likelyhasbetween(x,m,n) \
((((x)-~0UL/255*(n))&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)

この手法は、高速の事前テストに適しています。もう1つの操作（定数mとnに対して合計8）を必要とするが、正確な答えを提供するバリエーションは次のとおりです。

#define hasbetween(x,m,n) \
((~0UL/255*(127+(n))-((x)&~0UL/255*127)&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)
于 2012-04-07T06:07:13.473 に答える
2

x、yは、次の{x0<x<x1 and y0<y<y1}場合は長方形になります{x0<x and x<x1 and y0<y and y<y1}

ビット演算子を使用して<をシミュレートできる場合は、問題ありません。

バイナリで何かが<であるとはどういう意味ですか？検討

a: 0 0 0 0 1 1 0 1
b: 0 0 0 0 1 0 1 1

上記では、a> bです。これは、bの対応するものが0である最初の1が含まれているためですmyBit!=otherBit。（==またははequiv、および/または/ notで表すことができるビット演算子です）

ただし、1ビットから多数ビットに情報を伝播するための何らかの方法が必要です。そこで、これを自問します。「ビット」演算子のみを使用して関数を「コーディング」できますか。これは、と同等if(q,k,a,b) = if q[k] then a else bです。答えはイエスです：

  • q[k]をすべてのビットに複製することで構成されるビットワードを作成します。これを行うには、2つの方法が考えられます。
    • 1）kで左シフトし、次にwordsizeで右シフトします（効率的ですが、最後のビットを複製するシフト演算子がある場合にのみ機能します）
    • 2）非効率的ですが、理論的に正しい方法：
      • qをkビット左シフトします
      • この結果とandそれを10000...0で取得します
      • これを1ビット右シフトし、右シフトされorていないバージョンを使用します。これにより、最初のビットが2番目の場所にコピーされます。単語全体が最初のビットと同じになるまで（たとえば64回）このプロセスを繰り返します
  • この結果を呼び出すmaskと、関数は(mask and a) or (!mask and b)次のようになります。のthビットがtrueのa場合、結果は次のようになります。それ以外の場合、結果は次のようになります。kqb

ビットベクトルc=を取り、関数a!=b and a==1111..1 and b==0000..0を使用してif、最初のビットが1であるかどうか、次に2番目のビットが1であるかどうかを連続してテストします。

a<b := 
  if(c,0, 
    if(a,0, B_LESSTHAN_A, A_LESSTHAN_B), 
    if(c,1, 
      if(a,1, B_LESSTHAN_A, A_LESSTHAN_B), 
      if(c,2, 
        if(a,2, B_LESSTHAN_A, A_LESSTHAN_B), 
        if(c,3, 
          if(a,3, B_LESSTHAN_A, A_LESSTHAN_B), 
          if(...
                  if(c,64, 
                    if(a,64, B_LESSTHAN_A, A_LESSTHAN_B), 
                    A_EQUAL_B)
                  )
             ...)
        )
      )
    )
  )

これにはwordsize手順が必要です。ただし、再帰的に定義された関数を使用するか、再帰が許可されていない場合は固定小数点コンビネータを使用して、3行で書き込むことができます。

次に、それをさらに大きな関数に変換します。xMin<x and x<xMax and yMin<y and y<yMax

于 2012-04-07T06:34:22.953 に答える
2

数値が有限の正の整数である場合は可能です。

とで表される長方形がある(a1,b1)とし(a2,b2)ます。ポイントが与えられると(x,y)、式を評価するだけで済みます(a1<x) & (x<a2) & (b1<y) & (y<b2)。したがって、問題は、式cに対応するビット演算を見つけることです。

数値ciのi番目のビットとします（これはマスキングとビットシフトcによって取得できます）。最大でビットを持つ数の場合、は、と同等ciであることを証明します。nc<dr_(n-1)

r_i = ((ci^di) & ((!ci)&di))  |  (!(ci^di) & r_(i-1))

証明：ciとdiが異なる場合、左の式が真になる可能性があります（に依存します） 。そうでない場合、右の式が真になる可能性があります（次のビットの比較に((!ci)&di)依存します）。r_(i-1)

この式((!ci)&di)は、実際にはビット比較と同等ci < diです。cしたがって、この漸化式はtrueを返し、小さいと判断できるまで左から右にビットごとに比較しますd。

したがって、比較演算子に対応する純粋なビット演算式があり、純粋なビット演算で長方形内の点を見つけることができます。

編集：実際には条件ステートメントは必要ありません。展開してr_(n+1)から完了します。

于 2012-04-07T06:51:53.950 に答える