5

AND、OR、および NOT 演算子のみを使用して 2 つのオペランドを比較し、ジャンプを使用せずに true/false (-1、0) を返すロジックを作成することは可能ですか? もしそうなら、私には不可能に見えるので、ヒントを教えてください。本「The Elements of Computing Systems」のアセンブリ言語でeq、lt、およびgtを実装しようとしています。

4

7 に答える 7

6

ビット単位の論理演算子のみを使用している場合、比較演算から-1または0（または、さらに言えば1または0）の結果を取得することは不可能であり、キャリーが失われる場合は加算/減算します。

  • ビット演算子の場合、結果のビットnは、2つのオペランドのビットnのみに依存します。

  • さらに、2進加算がどのように機能するかを検討してください。結果のビットnは、各オペランドのビットn、およびビットnの右側のビット（キャリーを介して）の影響を受ける可能性があります。ただし、オペランドのビットnの左側にあるビットの影響を受けることはありません。（これは、2つの偶数を追加しても奇妙な結果は得られないという観察結果の一般化と見なすことができます。）

  • 単一の加算またはビット単位の演算では、オペランドのビットnの左側から結果のビットnに情報を伝播できないため、加算またはビット単位の演算の合成もできません。減算（ここでは2の補数を想定）は、まさにそのような構成と見なすことができます：xy = x +（NOT y）+1。

したがって、2 == 2の場合は0の結果を取得できませんが、2 == 4の場合は-1（または1）を取得できます。たとえば、目的の結果のビット0はそれぞれの場合で異なりますが、結果はいずれの場合も同じである2つのオペランドのビット0。

真と偽の値が一番上の（つまり左端の）ビットだけが異なる場合は、それを行うことができます。

たとえば、8ビット値の場合：trueの場合は0x80を使用し、falseの場合は0を使用します。次に、x == yとして実装できます(NOT((x - y) OR (y - x))) AND 0x80。

最初に述べた問題は、使用可能な操作が右シフトを含むように拡張された場合、またはADD操作が結果の下部に追加される可能性のあるキャリーを生成できる場合に解決できます。

于 2010-01-22T01:12:38.383 に答える
2 
XOR a, b

aとbが等しい場合は0になり、そうでない場合はゼロ以外になります。

SUB a, b
AND a, SIGN_BIT

（ここで、SIGN_BITは、...符号ビット以外のすべてを削除するためのマスクです）

aがbより大きい場合はゼロになり、aがb以下の場合はゼロ以外になります（2が完全であると仮定）。

于 2010-01-21T22:01:31.523 に答える
1

これが純粋な理論上の質問である場合に備えて、有限のオペランドセットを操作しているため、可能なすべての関数はOR、AND、およびNOTのみを使用して表現できます。

詳細については、選言標準形を参照してください。

実用的な目的のために、アノンの答えはより有用です:-)..。

編集：私の理論的な答えでさえ真実ではないかもしれません：出力ワードの各単一ビットが入力ビットのすべてのビットに依存するため、この問題に選言標準形を適用するにはシフト操作が必要になります。AND、OR、NOT、および算術を使用してシフトを実装する方法をまだ理解していません（そして、それが可能かどうかはわかりません...）

早すぎる答えの否定的な例として、私は投稿を残します...

于 2010-01-21T22:05:58.870 に答える
1

A Equal B は、xor で表すことができます。 

(A AND (NOT B)) OR ( A AND (NOT B))

これは、A==B の場合は 0 を出力し、そうでない場合は != 0 を出力します。

A が B 未満の場合は、 (A - B AND SIGN_MASK) を使用できます。

ここで、SIGN_MASK は符号ビットを除くすべてをマスクします。MAX_NEGATIVE_INTEGER の真の値と 0 の偽の値が得られます。

大なり小なりから自明に構築できる

于 2010-01-21T22:14:41.087 に答える
0

私たちは同じ本を読んでいて、ちょうどこの問題にぶつかっています。

私たちが見つけた最善の解決策は、一意のラベルを生成し、JEQ コマンドを使用して予想されるラベルにジャンプし、完了したらさらに下のラベルにジャンプすることでした。

擬似コード:

if they're equal, jump to EQUAL

// not equal section
push constant false
jump to DONE

// equal section
(EQUAL)
push constant true

// done section
(DONE)

これを (Ruby で) 具体的にどのように実装したかを次に示します。

于 2012-05-28T05:50:53.813 に答える
-1

履歴のある時点以降のx86CPUには、「条件付き移動」操作がありました。

于 2010-01-21T22:08:30.617 に答える
-1

あなたが話しているアセンブリ言語のすべての算術演算には、演算の結果 (=0? および >0?) に基づく条件付きジャンプの可能性があり、これを使用して目的のブール結果を得ることができます。

于 2010-01-30T12:25:07.493 に答える