XOR

 (chiark.greenend.org.uk)
1 ポイント 投稿者 GN⁺ 2025-02-19 | 1件のコメント | WhatsAppで共有
  • XORは、2つのビットが互いに異なるときに1になる演算であり、排他的OR・不等・条件付き反転・mod 2の加算/減算を1つの動作として結び付けて理解できる
  • 整数に対するビット単位XORは各桁を独立に処理してビットごとの差分を明らかにし、桁上がりのない2進加算のように動作しながら、交換法則・結合法則・0の単位元・自己逆元という性質を保つ
  • 暗号では平文とキーストリームを結合するために使われ、かつてのピクセルグラフィックスでは同じ図形をもう一度描いて消す方式により、メモリとCPUの負担を減らしていた
  • 半加算器の恒等式、ビット交換、3回のXORによるスワップ、Nimゲームの勝利条件のように、差分を作って再び打ち消す計算でXORの性質が直接活用される
  • 集合の対称差、指数2の群、nim-sum、GF(2) 上の線形代数や多項式へとつながり、Hamming符号・CRC・AES・GCM・Classic McElieceのような誤り検出・訂正および暗号技術とも結び付く

XORの基本的な意味

  • XORは2つの入力ビットと1つの出力ビットを持つブール演算であり、真理値表は 00→0、01→1、10→1、11→0 である
  • “exclusive OR”として見ると、2つの入力のうち一方だけが真のときに1で、両方が真なら0である
  • “not equals”として見ると、a XOR b は a ≠ b と同じで、2つのブール値が異なるときに1を出す
  • 条件付き反転として見ると、a=0 のときは b をそのままにし、a=1 のときは b を反転する
    • 同じ理由で、b を制御入力と見て a を反転する解釈もできる
  • パリティの観点では、入力中の1の個数が奇数かどうかを示す
    • 2ビットでは a+b mod 2 と同じである
    • a-b mod 2 とも同じである
    • 複数の値をXORすると、全入力中の1の個数が奇数か偶数か分かる

XORの代数的性質

  • XORは交換法則と結合法則を満たす
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • 長いXORのリストでは、順序や括り方は結果に影響しない
  • 0はXORの単位元である
    • a XOR 0 = 0 XOR a = a
    • 長いXORのリストでは0を取り除いてよい
  • すべての値は自分自身に対する逆元である
    • a XOR a = 0
    • 同じ変数が2回出てきたら、その2項をまとめて取り除ける
    • (a XOR b) XOR b = a のように、すでに混ざった値から既知の項をもう一度XORして取り除ける

整数に対するビット単位XOR

  • 整数のビット単位XORは、2つの整数を2進数として扱い、各桁のビットを独立にXORする
  • 単一ビットXORの性質は整数にもそのまま適用される
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • a XOR 0 = a
    • a XOR a = 0
  • ビット単位XORは2つの整数のビットごとの差分を示す
    • a=b なら a XOR b = 0
    • a≠b なら少なくとも1ビットが異なるため a XOR b ≠ 0
    • 結果値の1ビットは、2つの入力が互いに異なる位置を表す
  • ビット単位XORは条件付きビット反転器とも見なせる
    • 制御値の1ビットの位置だけでデータビットを反転する
    • ASCIIと一部の後続エンコーディングではラテン大文字と小文字が1ビットだけ異なるため、文字値に32をXORすると大文字小文字を切り替えられる
    • この規則はすべてのUnicode文字に適用されるわけではなく、大文字小文字の概念がない文字や、この規則に従わない文字も多い
  • ビット単位XORは桁上がりのない2進加算と同じである
    • 各桁でのみmod 2加算を行い、次の桁へ桁上がりを伝えない

暗号におけるXOR

  • 暗号では、平文と同じ長さのキーストリームを作り、平文のバイトやワードとキーストリームを結合して暗号文を作る方式が使われる
  • この結合段階では一般にXORが使われる
    • 受信者は同じキーストリームをもう一度XORして元の平文を復元できる
    • 送信者と受信者が同じ演算を使う点も少し便利である
  • キーストリーム自体を作る方法は、より複雑になり得る
    • one-time padはメッセージ全体のサイズ分の真の乱数データを使い、解読不能だが、ほとんどの目的には非常に非実用的である
    • 通常はストリーム暗号やcounter modeで動作するブロック暗号が、小さな鍵から必要な長さのキーストリームを生成する
  • この方式は良いキーストリームがあるとき機密性を提供できるが、メッセージ改ざんを検出する完全性は提供しない
    • 完全性保護は別の問題である
    • 初心者の暗号システム設計で完全性を抜かすのはよくある誤りであり、より複雑な暗号化方式でも誤った結果を招く
  • ハードウェアでは加算よりXORの方が単純である
    • 加算はビット間の桁上がり伝播が必要で、チップ面積と時間がより多くかかる
    • XORは桁上がりがないため、カスタム回路ではより低コストである

XOR描画とピクセルグラフィックス

  • 1980年代の家庭用コンピュータは、画面のピクセル当たりビット数とRAMが限られており、画面全体を2枚分保存するのは難しかった
  • 動くオブジェクトをXORで描くと、同じオブジェクトをもう一度描くだけで元の画面を復元できる
    • ピクセル値 S と動くオブジェクトのピクセル M をXORして C を作り、後で同じ M を再びXORして S を回復する
  • 複数のピクセルが1バイトにpackedされていたり、bit plane構造を使う画面では、加算ベースの合成は扱いにくい
    • 通常の加算では、あるピクセルの桁上がりが次のピクセルへ渡る可能性がある
    • XORには桁上がりがまったくないため、この問題がない
  • XORで線を描くと、2本の線が交差したピクセルは2回反転されて背景色に戻り、小さな傷のように見えることがある
    • この傷は、1本の線を消すときに別の線を壊さないための代償として受け入れられていた
  • XOR描画は単純なアニメーションにも有利だった
    • 新しい線を1本描き、古い線をもう一度描いて消せば次のフレームになる
    • 現在画面の全ピクセルや全線を描き直す必要がなく、メモリとCPUの使用が少ない
    • 1981年のゲーム Qix の動く線や、初期GUIのウィンドウ移動時の輪郭線にもこの方式が使われた

半加算器の恒等式

  • 1ビット加算で a+b の下位ビットは a XOR b、上位ビットは a AND b である
  • 同じ関係は整数のビット単位演算にも成り立つ
    • a + b = (a XOR b) + 2 × (a AND b)
    • a XOR b は桁上がりなしに足した値であり、a AND b は各桁で発生するはずだった桁上がりビットを含む
  • この関係は半加算器の恒等式と見なせる
    • ハードウェアの半加算器はANDゲートとXORゲートで、2ビット加算の桁上がりと下位ビットを作る
    • 整数全体の加算を単純演算だけで作ったわけではなく、右辺の + が桁上がり伝播を仕上げる
  • オーバーフローなしで2つの整数の平均を求めるとき、この恒等式を使える
    • 単純に a+b の後で右シフトすると、33ビットの和の最上位ビットを失う可能性がある
    • carry flagやRRX/RCRのような命令がない、または扱いにくいCPUでは、(a XOR b) >> 1 + (a AND b) という形が代替になる
    • 例としてMIPS、RISC-V、DEC Alphaにはcarry flagがなく、初期のArm ThumbにはRRXが欠けていた
  • XOR命令がないCPUでは、この恒等式を逆にしてXORを作れる
    • a XOR b = (a + b) − 2 × (a AND b)
    • 1970年代のData General CPUにはANDはあったが、bitwise XORはなかった

ビットと値のスワップ

  • 2つのビットを入れ替える問題は、2つのビットが同じなら何もする必要がなく、異なるなら両方のビットを反転する問題に帰着する
  • XORとシフトを使うと、2つのビットが異なるかを見つけ、必要な場合に両方の位置を反転できる
    • diff_all = input XOR (input >> distance) で一定距離だけ離れたビットペアの差分を計算する
    • AND で関心のある位置だけを選び出す
    • 選択された差分を別の位置へ複製したうえで入力にXORし、必要な場合だけ2つのビットを反転する
  • 同じ距離だけ離れた複数のビットペアをまとめて入れ替える場合にも、同じ方式を使える
    • 1ビットのマスクではなく、複数のビットを含むマスクを使う
    • Beneš networkは、複数段階で同じ距離の多くのペアを交換し、任意の順列を表現できる
  • 2つの値全体を入れ替える3回のXORによるスワップも可能である
    • a = a XOR b
    • b = b XOR a
    • a = a XOR b
    • 一時変数がなくても2つの値が互いに交換される
  • 3回のXORによるスワップには**エイリアシング(aliasing)**の問題がある
    • 異なる変数を入れ替えるときは動作する
    • 配列の同じ要素を自分自身と入れ替える場合のように、2つの名前が同じ保存場所を指すと、値が0になり得る

NimゲームとXOR

  • Nimは、複数の山から順番に1つの山を選び、1個以上好きな数だけ駒を取り除くゲームであり、それ以上動けなくなったら負けである
  • 単純版のNimで負ける局面は、すべての山の大きさのビット単位XORが0である局面である
  • XORが0の局面である山の大きさ a を別の値 b に変えると、全体のXORは a XOR b の分だけ変わり、a≠b なので0ではなくなる
  • XORが0でない局面では、全体のXOR値 x の最上位の1ビットを見て、そのビットが1である山を選び、サイズを pile XOR x まで減らすと、全体のXORを0にできる
  • 例として山の大きさ12、10、3は2進数で 1100、1010、0011 であり、XORは 0101 である
    • 最大の山12だけが 0101 をXORしたとき9に減る
    • 勝つ手は12から3個取り除いて9にすることである

XORのように見える数学構造

  • 集合論の対称差 X∆Y は、ある要素が2つの集合のうちちょうど一方だけに属するとき含める演算である
    • 要素の所属有無をブール値として見ると、対称差はXORと同じである
    • したがって交換法則や結合法則のようなXORの性質を共有する
  • 群論で指数2の群とは、すべての元が自己逆元である群である
    • このような群の演算は結合法則を満たし、標準的な演習として交換法則にも従う
    • 同じ元が2つ一緒にあると打ち消される点がXORに似ている
    • すべての指数2の群は、何らかの {0,1} 値関数のビット単位XORの形として理解できる
  • Sprague-Grundy解析では、多くのimpartial gameの局面にGrundy numberを割り当てる
    • 複数の下位ゲームを1つに合わせたcompositeのGrundy numberは、各構成ゲームのGrundy numberをbitwise XORした値として計算される
    • game theoryでは非負整数のbitwise XORをnim-sumと呼ぶこともある
  • 体 GF(2) は元が0と1だけの有限体である
    • 加算と減算はXORのように動作する
    • 乗算はANDのように動作する
    • したがって a AND (b XOR c) = (a AND b) XOR (a AND c) が成り立つ

GF(2)上の線形代数と誤り訂正

  • GF(2) 上のベクトルと行列は成分が0または1である構造であり、ベクトルや行列の加算は成分ごとのXORである
  • 行列 M にベクトル v を掛けることは、v の1成分が選んだ M の列をXORで合計することと同じである
  • 誤り訂正符号は、mビットのメッセージをより長い nビットのコードワードへ拡張し、一部のビット誤りを検出または訂正できるようにする
    • 有効なコードワード同士が多くのビットで異なっていれば、少数のビット誤りで別の有効なコードワードに変わることはない
    • 2つの有効なコードワードが最小 k ビット異なるなら、k より少ない誤りは検出可能で、k/2 より少ない誤りは最も近いコードワードを探して訂正可能である
  • 線形符号は GF(2) 上のgenerator matrixとcheck matrixを使う
    • senderはgenerator matrixで mビットのメッセージを nビットのコードワードへ拡張する
    • receiverはcheck matrixで受信コードワードが有効か確認し、誤りがあればsyndromeを得る
    • 同じ誤りパターンはメッセージに関係なく同じsyndromeを生成する
  • Hamming codeは、符号長 n が 2^d−1 の場合の例である
    • n=15 なら、15個のビット位置を0001から1111までの4ビットの非ゼロ数で番号付けする
    • 受信者は1であるビットのインデックスをすべてXORし、結果が0なら有効なコードワードである
    • 1ビットが反転すると、XOR結果がそのまま反転したビットのインデックスになるため、lookup tableなしで1ビット誤りを修正できる
    • 15ビットのHamming codeは11ビットのデータを含み、4ビットを誤り訂正に使う

GF(2)多項式、CRC、より大きな有限体

  • GF(2) 上の多項式は係数が0または1である形式的多項式であり、加算は同じ次数の係数同士をXORすることと同じである
  • 多項式乗算は通常の多項式と同様に部分積を作り、係数をmod 2で減らす方式である
    • この表現をビット列として見ると整数乗算に似ているが、部分積を合わせるときに通常の加算ではなくcarryなしのXORを使う
    • x86は CLMUL を含むcarryless multiplication命令を提供し、Armはpolynomial multiplication系の命令を提供する
  • CRCは、GF(2) 多項式除算の余りをチェックサムとして使う方式である
    • 送信メッセージのビット列を大きな多項式 M と見なし、合意された多項式 P で割った余り M mod P を保持する
    • Ethernetと同様のネットワークパケット検証に使われる
    • CRCは誤りを訂正せず検出のみを行い、ほぼすべての伝送が正常で、まれにビット反転やノイズが生じる状況に合っている
  • より大きな有限体は、GF(p) 上の多項式をirreducible polynomial Q で割った余りの構造として作れる
    • Q の次数が d なら、新しい有限体は p^d 個の元を持つ
    • p=2 の場合、irreducible polynomialはビットパターンを整数のように書け、その数列は OEIS A014580 に登録されている
  • 2のべき乗サイズの有限体は、複数の暗号技術に登場する
    • 2^8 サイズの有限体はAESとTwofishの中核的な構成要素である
    • 2^128 サイズの有限体はbulk encryptionとintegrity protectionを組み合わせるGCMで使われる
    • 2のべき乗サイズの有限体は、一部のelliptic-curve cryptographyや、post-quantum方式であるClassic McElieceのdecodingアルゴリズムにも登場する

関連記事

1件のコメント

 
GN⁺ 2025-02-19
Hacker Newsの意見

  • 私の好きな呪われた XOR テクニックは XOR 二重連結リスト: https://en.m.wikipedia.org/wiki/XOR_linked_list
    各ノードは次/前ポインタを別々に保持する代わりに、その両方を XOR した単一の値を保持する。当然ながら有効なポインタではないが、走査時に前のノードポインタと結合ポインタを XOR すると次のノードポインタが得られ、双方向の走査も可能になる。なんだか違法っぽく感じる

    • 通常の二重連結リストと比べて、要素のアドレスしか持っていない、あるいは挿入/削除に対して安定なイテレータしかない場合に、その要素を削除する能力を失ってしまう。しかも、これが二重連結リストを使う主な理由であることが多い
      それほど本質的ではない欠点として、標準に厳密に従う C で XOR 連結リストを書くのはひどく面倒。標準では、同じポインタを整数にキャストしたときに常に同じ整数になることが保証されていないため、実質的には正規化された整数キャスト版を維持するために、すべてを uintptr_t にしなければならない
    • 64ビットプロセッサでも、ほとんどのアプリは 4GB 未満の RAM で十分だと考えるなら、32ビットアドレス空間だけでさらに格納領域を減らせる
      さらに進めて、16ビットの近距離/相対ポインタも可能かもしれない。データ指向設計と相性が良い可能性があり、64K 要素のブロックを置き、内部要素は uint16 インデックスで指すといったやり方ができる
    • こうすると ガベージコレクタは嫌がるだろう。少なくともこのデータ構造をゴミだと判断しそう
    • なぜこの手法を使いたくなるのか気になる
    • これはポインタというより、2つのポインタの差を保存するのとあまり変わらない。差を保存しても当然ながら双方向走査は可能

  • 見落としていた点がある。XOR は 3-wise 独立な線形ハッシュ関数でもあり、ブール関数の解の確率的な近似一様サンプリングや個数カウントに使える。本当に有用で、確率的ではあるが証明付きの個数を返すカウンタの構築に使われている。もっと分かりやすい説明はここにある https://www.msoos.org/2018/12/how-approximate-model-counting...
    基本的には、毎回解空間をほぼ正確に半分にする。だから XOR 条件を追加し続けて、たとえば解が 10 個残ったら、追加した XOR の数を k として、10 に 2^k を掛ければよい。毎回半分ずつ減るので、10 個程度の水準にもすぐ到達でき、スケーラビリティが高い
    関連論文は https://arxiv.org/abs/1306.5726 と https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf にあり、ツールは https://github.com/meelgroup/approxmc と https://github.com/meelgroup/unigen にある。前回のモデルカウンティング競技会では、正確なカウンタと組み合わせたときに他の競合を圧倒しており、スライドは https://mccompetition.org/assets/files/2024/MC2024_awards.pd... にある

  • 私の好きな XOR の逸話のひとつは、Oxide、Joyent、Sun の Bryan Cantrill がこの発表 https://speakerdeck.com/bcantrill/oral-tradition-in-software... とこの動画 https://www.youtube.com/watch?v=4PaWFYm0kEw で話していたもの
    リンクを開かなくてもよいように要約すると、Sun にいたとき同僚の Roger Faulkner と C に論理 XOR がない理由を話していて、Faulkner は短絡評価ができないからだと言い、Brian はそれを変だと思った。そこで Roger が Dennis Ritchie にメールで尋ねたところ、Ritchie が Faulkner の説明が正しいと確認した。Cantrill の語り口も面白いが、本人に直接聞けたという点が驚き

    • DMR は驚くほど親切で、よく助けてくれて、近づきやすい人だった。80年代半ば、学部生だったころに PDP-11 ではなく Interdata 8/32 へ Unix v6 を移植した「最初」の事例を読み、アーキテクチャ情報がもっとあるか dmr@research.att.com にいきなりメールを送った
      当時は Google もなく、大学図書館にも資料がなかったが、数日後に郵送先住所を尋ねられ、数週間後には 命令セット要約マニュアル のコピーが郵便受けに届いた。IBM 360 系っぽい感じで、今でも持っている
    • C には論理 XOR があり、それはまさに != 演算子。ほかの論理演算子と違って、引数を単一の真理値に正規化する必要があり、C のブール変換イディオム !! と相性が良い
    • 「短絡評価ができないから」というのが、なぜ演算子追加の障害になるのか理解できない。誰か説明してほしい
    • その話題は 37:18 から始まる
    • C には 40年以上前から ビット単位 XOR 演算子 ^ がある: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

  • 自動車の絵文字を 0x20 と XOR すると、つまり「小文字化」すると、通行人禁止の絵文字になることを今日知った。偶然にしてはあまりにもぴったりで、意図的なのか知っている人がいるのか気になる
    あまり押し進めると、自動車の絵文字の小文字が「通行人禁止」の標識だという妙な考え方もできる

    • HN の絵文字削除コメント処理を避けるには、こうやって確認できる:
      >>> from unicodedata import lookup, name
      >>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
      'NO PEDESTRIANS'
    • 自動車の小文字は ゴーカート っぽい
    • :tada: → :tophat:, :rocket: → :mountain_cableway: も可能

  • XOR を説明するときに使いやすい現実の比喩は、家の階段にある 照明スイッチ。下に 1 つ、上に 1 つスイッチがあって、どちらも同じ照明を制御する
    最初は両方ともオフの位置にあるが、下のスイッチを入れると明かりがつく。階段を上がって上のスイッチを入れると、2 つのスイッチはどちらも「オン」の位置なのに明かりは消える。片方だけが「オン」で、もう片方が「オフ」のときだけ明かりがつき、それ以外では消える

    • うちのオフィスの電気工事士は配線を間違えたのかもしれない。部屋にスイッチが 2 つあるが、考えてみると XOR というより AND ゲート のように動く。居間の 2 つのスイッチは確かに XOR のように動く

  • この論理関数に XOR、つまり「排他的 OR」という名前がよく使われるのが本当に気に入らない。ほとんどの場合、実際の意味は「2 で割った剰余の和」、つまり パリティ であって、排他的 OR ではないからだ
    「2 で割った剰余の和」/パリティと「排他的 OR」は別の論理関数で、入力オペランドが 2 個のときだけ偶然一致する。2 以下の奇数が 1 つしかないからだ
    入力が 3 個以上のとき、多くの人が XOR と呼んでいるものは、実際には 1 の入力が奇数個あるときに 1 になるパリティである。一方、排他的 OR は入力が 3 個以上のとき、ちょうど 1 つの入力だけが 1 で、残りがすべて 0 の場合にのみ 1 になる関数である
    コンピュータハードウェアでは、パリティのほうが排他的 OR よりはるかに重要だ。主な理由は、2 を法とする加算が、より大きな数の加算を実装するための構成要素として使われるからだ。逆に数学では、排他的 OR のほうがパリティよりはるかに重要である
    たとえば、ある述語が集合の一部の要素、すべての要素、または唯一の要素について真であることを表す量化子は、それぞれ OR、AND、排他的 OR に基づく。自然言語の “or” は、常に包含的 OR か排他的 OR を意味し、多くのプログラマが XOR と呼ぶパリティを意味することはない
    プログラミングで排他的 OR の論理関数そのものを計算することはまれだが、プログラムの動作説明ではよく使われる。たとえば select/case/switch 複合文で最初の文、または 2 番目の文、または 3 番目の文のいずれか 1 つが実行される場合や、ユニオン/合併型変数の現在の値が取りうる型を説明するときなどである

    • 電気技術記号の標準である IEC 60617 はこの点を正しく扱っている。XOR ゲートは =1、パリティゲートは 2k + 1 と表記する。ただし PCB や FPGA 向けの回路設計ソフトウェアを使うと、期待したものと違うものが出てきて、いまだに引っかかることがある
    • 数学で言っていたのは 一意存在量化 と呼ばれ、専用の記号 ∃! がある
    • 入力が 3 個以上のとき、「排他的 OR」がちょうど 1 つだけ 1 のときに真になるという説明には根拠が必要だ
    • この解釈は本文のエッセイでも扱われている

  • Kademlia 分散ハッシュテーブル もある: kademlia distributed hash table。大きなアイデアは、各ノードに [0, 2^m) の範囲のランダムなビット列を割り当て、距離を XOR で定義することだ。ネットワーク全体を知らなくても、X から Y へ情報を素早く送る分散アルゴリズムを見つけたい
    数学だけでも動作を証明できるが、私の好きな視覚的直感はこうだ。開始ノード X がノード k を見つけたいとしよう。「X-距離木」を、葉のインデックスが 0, 1, 2... の二分木として定義し、各葉には X との距離を表すように X^leaf_index というラベルを付ける。たとえば dist(x, x) = x^x = 0 なので、元のノード X のラベルは一番左の葉 0 に置かれる
    区間 [2^i, 2^(i+1)) は、X-距離木のある部分木である。k までの距離がその区間に入るとわかっているなら、その中のあるノード Y に近似近傍として問い合わせる
    どの Y を選んでも、Y-距離木における結果の接頭部は、常に X-距離木で選んだ [2^i, 2^(i+1)) 部分木の何らかの順列になる。より正確には、labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)) とみなせる。インデックスは距離基準だが、ラベルは異なる場合がある
    Chord のような他の分散ハッシュテーブルとの比較については、数学的にも経験的にももっと厳密な資料がたくさんある。ただ、この視覚的直感は Kademlia の「対称性」が何であるか、つまり各自が自分だけのローカルな近傍と自分の部分木を持っているという感覚を与えてくれる
    一方 Chord は、双方向に実装するとメモリが 2 倍必要になり、実装もより危うく見え、このレベルの「分離性」を得るのが難しい。サイズ S の近傍スライディングウィンドウが常に動いており、ビットごとに 2^m 個の異なる近傍が存在する。ほとんどの近傍が似て見えても、すっきりはしない
    Kademlia には 1 + 2 + 4 ... + 2^m-1 個の近傍があり、全体が整然としている

  • 気になる人のために補足すると、この人は Simon Tatham's Portable Puzzle Collection のあの Simon Tatham である。知らないなら、オフラインで退屈したときに遊ぶのに向いている
    高校時代、これらでかなり時間を溶かした: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • 最近では、多くのカスタム最適化ソルバ、たとえば Ising Machine が XOR 問題でベンチマークを行っている。実際には、複数の XOR 節を解くことはガウス消去法で多項式時間で可能なので実用性はやや低いが、ソルバはいずれも指数的スケーリングを示すため、性能を見極めるには良い方法である。
    2つ目の興味深い実装は McEliece 暗号系 に関係している。1970年代の公開鍵暗号で、最近は耐量子性のため再び注目されている。復号攻撃は XOR 方程式集合の解を見つける問題だが、これも多項式時間で解ける一方、ハミング距離が公開鍵に含まれるある値と等しくなければならないという条件が付く

  • TI-83 のプログラミングをしようとして Z80 アセンブリ を学んでいたときは、機械語 1 バイトの重みが非常に大きかった。電卓全体の保存領域が 24KB しかなかったからだ。
    主アキュムレータレジスタ a を 0 に初期化するには LD a, 0 の代わりに XOR a を使っていた。算術命令では a が自動的にオペランドになるので、XOR a は a を自分自身と XOR し、命令全体が 1 バイトで済む。一方、0 を明示的に a にロードするにはリテラルの 0 を opcode に含める必要があるため、LD a, 0 は 2 バイト命令になる