2 つの数値の XNOR

XNOR (XNOR) ゲートは、2 つの入力を受け取り、1 つの出力を与えるデジタル論理ゲートです。その機能は、排他的 OR (XOR) ゲートの論理補数です。 2 つの入力が同じ場合、出力は TRUE になり、入力が異なる場合は FALSE になります。 XNOR ゲートの真理値表を以下に示します。

＃＃＃1つ＃＃＃ ＃＃＃出力＃＃＃ 10102 つの数値 x と y が与えられます。 2 つの数値の XOR を求めます。 例 例 1

B		1
1		1
0		0
0		0
1		＃＃＃問題文＃＃＃

リーリー リーリー

イラスト

リーリー

サンプル例 2

の中国語訳:

サンプル例 2

リーリー リーリー

イラスト

リーリー

方法 1: 暴力による方法

総当たりの方法は、2 つの数値のすべてのビットをチェックし、それらが同じかどうかを比較することです。同じ場合は 1 を加算し、そうでない場合は 0 を加算します。

疑似コード

リーリー

例: C 実装

次のプログラムでは、x と y のビットが同じかどうかを確認し、答えのビットを設定します。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量: O(logn)、走査はすべての logn ビットに対して実行されるため。

空間の複雑さ: O(1)

方法 2

XNOR は XOR 演算の逆演算であり、その真理値表も XOR テーブルの逆演算です。したがって、大きい方の数値のビットを切り替える、つまり 1 を 0 に、0 を 1 に設定し、小さい方の数値と XOR 演算を行うと、XNOR 数値が生成されます。

例 1

リーリー リーリー

イラスト

リーリー

サンプル例 2

の中国語訳:

サンプル例 2

リーリー リーリー

イラスト

リーリー

疑似コード

リーリー

例: C 実装

以下のプログラムでは、大きい数値のすべてのビットがトグルされ、小さい数値と XOR 演算されます。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量: O(logn)、toggle() 関数のトラバーサルのため

空間の複雑さ: O(1)

方法 3: ビットマスク

論理的に言えば、XNOR は XOR の逆演算ですが、XOR で補数演算を実行すると、先行ゼロも反転されます。これを回避するには、ビット マスクを使用して、不要な先頭ビットをすべて削除します。

例 例 1

リーリー リーリー

イラスト

リーリー

例 2

リーリー リーリー

イラスト

リーリー

疑似コード

リーリー

例: C 実装

次のプログラムでは、ビット マスクを使用して、x xor y の逆数から必要なビットのみを取得します。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

要約すると、2 つの数値の XNOR は、O(logn) の総当たり法から O(1) の最適な方法まで、さまざまな方法と時間計算量を使用して求めることができます。ビット単位の演算を適用する方がコストが低いため、総当たり法の複雑さは対数的になります。

以上が2 つの数値の XNORの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。