18

+、-、*、/ などの基本的な数学演算子を使用して XOR を実装するにはどうすればよいですか

更新:実際には、ブール値を持つ 2 つの行列の変化を追跡する必要があります。これは、各値を他のマトリックスの対応する値と XOR することで実行できます。ただし、Lp_Solve ライブラリは XOR 演算をサポートしていません。また、線形方程式のみを受け入れます。

4

9 に答える 9

15

(a − b)²

(a − b)² の 3D プロット

これは次の理由で機能します。

(a − b)² = a * (a − b) + b * (b − a)

ℤ₂ の乗算は結合 ( &) であり、1 - a否定 ( !) であるため、上記の式は の XOR と等価ですa, b ∈ {0, 1}。

(a & !b) | (b & !a)

以下の Pascal Cuoq によるコメントを参照して、これが線形方程式にならない理由を説明してください。

于 2010-03-05T08:33:52.967 に答える
8

Brown, G. and Dell, R., Formulating linear and integer linear programs: A rogues' gallery では、XOR の次の線形計画法を見つけることができます。

Z3 = Z1 XOR Z2

に解決

Z3 <= Z1 + Z2
Z3 >= Z1 - Z2
Z3 >= -Z1 + Z2
Z3 <= 2 - Z1 - Z2
于 2011-03-30T13:23:28.747 に答える
6

うーん………

それはそれほど単純ではありません。

XOR (X と呼びましょう) をモデル化するには、ロジックから始めます。

X = (A & !B) | (!A & B)

数学では、上記は次のように記述できます。

X = A*(1-B) + B*(1-A)

しかし、上記の式は非線形です (双一次項のため -- 線形性を維持するために、変数を互いに乗算することはできません)。

しかし！制約を使用できるため、上記の式を線形形式に書き直すことができます。

まず、用語を拡張します。

X = A*(1-B) + B*(1-A) = A + B - 2*A*B

ここで、A*B という用語 (本質的には A & B を意味します) を処理する必要があります。変数 H が論理条件 A と B を表すとします。これで AND 条件を次のように記述できます: (以下の引用された参照 PDF を参照)

H <= A
H <= B
H >= A + B - 1
H >= 0

線形 XOR の定式化

最後に、すべてをまとめましょう。これは、線形制約のみを使用した XOR 式です。

X = A + B - 2*H
H <= A
H <= B
H >= A + B - 1
H >= 0

複雑に見えることはわかっています（XORのような単純な操作の場合）。よりコンパクトな定式化が存在する可能性があります。

しかし、一般に、線形計画法のコンテキストで論理条件を記述することは複雑です。なぜなら、問題の理論的特性を破壊することを避けるために、通常、実行できる操作が厳しく制限されているためです。

参照

論理を線形に表現するための標準的な整数公式のリストについては、こちらを参照してください。 http://brblog.typepad.com/files/mipformref-1.pdf

編集：

H 制約がどのように「AND」論理条件をモデル化するかについての説明。基本的に、LP では、解決点で満たさなければならない不等式の制約を課します。ここで行っているのは、H を適切な値に「絞る」ためのトリックを実行することです。たとえば、タプル (A,B) = (0,0) が与えられた場合、H の制約は次のようになります。

H <= 0
H <= 0
H >= -1
H >= 0

上記の場合、H は区間 [0,0] に属しているため、H が取り得る唯一の値は 0 です。したがって、(A,B) = (0,0) => H = 0 となります。

(A,B) = (1,1) という別の例を試してみましょう。

H <= 1
H <= 1
H >= 1
H >= 0

上記から、1 <= H <= 1 は H = 1 を意味することがすぐにわかります。(A,B) = (1,1) => H = 1 が得られます。

等々。H 制約が「AND」条件を正確にモデル化していることがわかります。

于 2010-07-25T06:02:55.497 に答える
5

あなたは次のようなことをすることができますか？

(a + b) % 2
于 2010-03-05T08:55:35.487 に答える
0

排他的論理和は線形関数ですが、ブール関数に関する「線形」の定義は、多項式関数の場合と同じではありません。ライブラリのドキュメントを調べて、lp_solve線形ブール関数を処理できるかどうかを確認する必要があります。私が読んだことから、私はそれができるとは思わない。

編集：を使用するシンプレックスアルゴリズムをさらに調べた後lp_solve、私はあなたがやろうとしていることをあなたがすることができないとかなり確信しています。

于 2010-03-06T00:47:15.177 に答える
0

abs(A+B-1)。腹筋を行わない場合は、(A+B-1)*(A+B-1) で行う必要があります。

于 2010-06-17T16:24:00.697 に答える
0

これを使用できます：

Xor(n,x,y)=x+y - Pow(2,n+1)(floor((x+y)/Pow(2,n+1)));

いつ

x => Z コレクション内の数値で、正数、x>=0

y => Z コレクション内の数値で、正数、y>=0

n => はデータ ビット長で、たとえば 32 または 64 です。

pow(2,3)=> 2 2 2

床(1.6594565)=1または床(4562.21)=4562

于 2020-12-12T20:57:04.670 に答える