衝撃のXORとは？その秘密に迫る！
引用元：https://news.ycombinator.com/item?id=43087944
俺のお気に入りのカーストなXORトリック、XORダブルリンクリストってのがあるんだ。各ノードが次と前のポインタを別々に持つ代わりに、2つのXORの単一ポインタを格納するんだ。イレギュラーなポインタだけど、イテレーションのときは前のノードのポインタと組み合わせたポインタをXORして次のノードのポインタを取得するのさ。これで双方向に走査できる。ちょっとアブノーマルかもね。
これの欠点は、スムーズにアイテムを削除できる能力が失われることかな。ダブルリンクリストを使う理由はそれが多いから。あと、XORリンクリストをCで書くのは超面倒で、標準は同じポインタが同じ整数にキャストされることを保証してないから、uintptr_tにして、実質的に整然とした整数表現を維持しないといけない。
＞標準は同じポインタが同じ整数にキャストされることを保証しない。ポインタのサイズが整数のサイズと同じである保証もないよね。古いPowerPCではそうだった記憶がある。今はx86-64やAarch64が主流で、32ビットもまともで、以前の面白いワードサイズの機械はほとんど忘れ去られた。C標準は基本データ型のサイズに柔軟性を持たせるためのもので、標準が型間の関係だけを定義しているんだ。固定幅タイプがC99で標準化されるのに時間がかかったのは意外だね。
俺が言いたかったのは、一般的な整数のことで、例えばpとqが（たとえば）voidポインタでp == qなら、(uintptr_t)p == (uintptr_t)qになる保証はないってこと。NULLに対しても同様。ポインタが同じメモリ位置を指している複数の方法が存在する場合があるってことだ。XORリンクリスト操作はこう書くべきなんだ。
struct node { uintptr_t link; };
void prepend(uintptr_t head, struct node *n) {…}なんで、例えばheadをstruct entry *にできないんだ。uintptr_tとして公開する必要があるんだ。
へぇ、そういうことか。このリストが崩壊する可能性があるのは、ポインタが正確に先頭か末尾を指していても、XORに使うビット表現が違うと問題が起こるんだ。実際にこの現象を見たことがある？
この問題が実際に破損を引き起こすかどうか確かではないけど、同じポインタが異なる整数に変換されるのは確かだよ。サンプルコードも見る？
現代の64ビットマシンでは、sizeof(int) != sizeof(int*)ってのはかなり真実だね。でも、sizeof(uint64_t)やsizeof(long)が等しいという前提で動いてるコードが多いかも。
そうだね、もし前のポインタのペアを保持し続ければ、効率的な削除や挿入が復活するよ。隣接ポインタペアをWidePointer型としてカプセル化して、内部で動作させることもできるし。これで少し遅くなるかもしれないけど、スペースの節約になるし、他の操作が速くなる場合もあるかも。
ストレージをもっと減らせるかも。64ビットプロセッサを考えると、32ビットのアドレス空間で大抵のアプリに十分かもしれない。16ビットの近接ポインタとかも考えられるよ。データ指向デザインがうまく行くかもね。
＞64ビットプロセッサで、32ビットのアドレス空間が充分ってのは、Java仮想マシンが64ビットプラットフォーム上で使ってる32ビットの「圧縮オブジェクトポインタ」と関係があるね。8バイトアラインされているけど、32 GiBのメモリにアクセスできるんだ。
冗談言ってるのはわかるけど、ポインタとインデックスを混同するのはちょっと危険だね。16ビットのインデックスは全然問題ないけど、16ビットのポインタはかなりやばいよ。それに、32ビットのポインタは状況によってはいい最適化になる。Javaだと、オブジェクトのアライメント次第だけど、32GBや64GBを超えない限りは32ビットポインタを使うとメモリをかなり節約できる。
16ビットの相対ポインタは、16ビットのインデックスと同じくらい役に立たないか、ひどいかのどちらかだね。
範囲が限られた相対ポインタってあんまり良くないもので、基準がもう隣にないことも簡単に起きる。64k要素の制限があるよりもずっと厄介なことが多いんだ。
Rustの借用チェッカーみたいなのがあれば、参照やポインタがちゃんと生存するべき期間だけ存在するようにしてくれるよ。
つまり、”地雷”っていうのはデータが近くにないから使いにくい状況のことだよ。最初に書いたときは正しいかもしれないけど、ちょっとしたアップデートでそれが変わることもある。借用チェッカーがそんな状況にはあまり役に立たないと思うな。
そうだね、柔軟性は失われる。それがパフォーマンス向上の代償だよ。
こう考えてみて：16ビットのインデックスは滅多に価値がない。16ビットのポインタは、トラブルが10倍で状況が広がるのは20％だけ。それだけの価値はないと思うな。そんなに似たようなものじゃないよ。
相対ポインタとインデックスはほぼ同じだよ。違うのは使いやすさ。大抵はどちらも役立たないと思う。
インデックスは同じメモリ割り当てに含まれるから、大きな違いがある。配列のサイズに制限をかけているだけで、メモリ割り当てが複雑にならないんだ。もし大きいのが必要なら、いてもたってもいられないってわかるからね。小さなポインタサポートや整数をポインタに変換するサポートも言語に必要ないし。
要するに、ポインタを使う代わりにインデックスを使ってるんだね。インデックスにはメリットがあって、もっとコンパクトで位置に依存しない。でも、ベースポインタが必要で、計算も少し増える。自分のアロケータが必要になるし、普通のヒープアロケータはオブジェクトへの任意のポインタを渡しちゃうから。
ポートスキャンの効率的なデータ分析を考えてるんだけど、32個のポートの状態をビットフィールドで管理するってアイデアが面白いよね。IPv4アドレスを使って、ビットシフトで状態を挿入したりチェックしたりできるから、かなり速いしメモリも節約できる。全体のIPv4スペースで16GiBのメモリを使うところも魅力的。 確かに25個の512MB配列に分けた方が良いかもね！それで分析しやすくなりそう。アドレス数も224«24にするともっといいかも。 ＞25個の512MB配列になるって？ 8086が64本のアドレスピン持ってるの？それとも冗談だった？ これやるとガーベジコレクタに嫌われるかも。データ構造がゴミって見なされるだろうね。 なんでそんなトリックを使う必要があるの？ リンクリストのストレージオーバーヘッドを減らすためさ。64ビットシステムだと要素ごとに8バイト節約できるんだ。 ＞次ポインタと前ポインタをそれぞれ別で持つ代わりに、それをXORで一緒にするって？ そうだけど、TFAでも述べられている通り、違いを保存するには追加のビットが必要なんだ。XORなら元のポインタのサイズと同じだから、扱いやすい。確かに、ポインタの差分だけで双方向のリンクリストを作るのはちょっと違法感あるよね。 ＞前後のポインタの違いを保存するには追加のビットが必要って？ いやいや、32ビットポインタの前提で、通常の符号なし算術で足し算や引き算をするから、モジュロ２^32になるよ。要するに、足し算や引き算、XORがすべて逆操作できるのと同じトリックが使えるってこと。XORで数値を操作するのが面白いのは、その操作が自分自身の逆になるところだよ。 XORと差分の大きな違いは、XORの対称性のおかげで、リストを前後に歩くのに同じコードが使えることだね。 「640Kで十分」って時代のトリックを思い出すなぁ。今は制約の厳しいデバイス向けに取っておく方がいいと思う。 忘れちゃだめ！これは3次独立の線形ハッシュ関数なんだ。確率的にほぼ均一なサンプリングや論理関数の解のカウントに使えるって超便利だよ。解の空間を毎回半分にするから、例えば10個の解が必要になるまで加算を続けていくと、10に２^kを掛けるだけ！スゴくない？ これはXORの最もセクシーな使い方だよ！ XORに関するお気に入りの話は、Bryan CantrillがSunでの経験を語ったことだよ。彼が同僚とCのXORがない理由を話していたら、理由を確認するためにDennis Ritchieにメールを出すことになったんだ。そのやり取りがおかしくて印象に残っている！ DMRは本当に親切で助けてくれた人だな。80年代中頃にUnixの最初の他のポートについてメール送った時、数週間後にインストラクションセットのマニュアルが送られてきた。今でも持ってるよ。 Cには論理的なXORがあって、それは’!=’演算子だよ。他の論理演算子とは違って、引数を単一の真理値に正規化する必要があるんだ。Cの真理値への変換演算子’!!’と組み合わせて、うまく使えるよ。 プログラミング20年やってて、仕事の面接でテストに失敗したことがある。 二重否定はいらないよ：！foo != !bar。 そうだけど、こういう変な書き方を使うと人を混乱させるかもね。 それはビット単位のxorだよ。 それはビット単位のもので、論理的なものじゃないよ。 Faulknerはショートサーキットできないからだって言ったけど、これの何が問題になるのか分からないな。詳しく教えて。 論理専用の排他的OR演算子を追加する利点はないよ、||や&&とは違って。 トピックは37:18から始まるよ。 ”Cについて、論理的なXORがないことを同僚と話してた。”Cは40年以上前からビット単位のXOR’^’を持ってるよ。 すごい。車の絵文字を0x20でXORすると”歩行者禁止”の絵文字になるって。意図的かどうか分かる人いる？ HNの絵文字取り除き機能を満たすために： 車の小文字って言ったら、ゴーカートかな。 🎉 → 🎩 XORの例えとして、家の階段のライトがわかりやすい。下のスイッチを入れたら点灯、上で入れたら消灯。でもどっちかがオフだと点灯。 オフィスの電気工事が違ってるのかも。部屋にスイッチ2つあるけど、ANDゲートみたいになってるよ。リビングは間違いなくXORだな。 XORのスイッチってトリックだね。知っててもなかなか理解できない。叔父が工事したとき、逆にスイッチをつけてたのを思い出した。正しくつけないとANDスイッチになるよ。 XORって名称が嫌い。ほとんどの場合、パリティのことを指してるから。2つの時だけ一緒だけど、3つ以上はパリティだからね。 IEC 60617では、XORゲートは=1とパリティゲートは2k + 1ってちゃんと区別されてるんだ。だけど、設計ソフトでは時々期待外れがあるよ。 数学における「exclusive or」は重要で、独自の記号もあるんだ。 ＞「3つ以上の入力の時、exclusive orは1つの入力だけが1の時のみ値が1になる」 過去の論理学や文法のテキストを探せば、‘or’の使い方についての意味が議論されている部分がいくらでもある。でも、引用はいらない。英語のコンテキストで十分。 数学は英語じゃないんだよ。整数の環を指にはめてるわけじゃないし、実数のフィールドでサッカーもできない。XORが何を意味してるのか混乱しているフリをしているのは君だけだね。意味はそのままなんだから、こんな意味論の議論が君にとって何の役に立つの？ この解釈はエッセイ内で触れられてるよ。 Kademlia分散ハッシュテーブルに関する話だね。各ノードが[0, 2^m)の範囲でランダムなビットを持って距離をXORで定義する。XからYに情報を速く取得する分散アルゴリズムを探してる。最初のノードXから目標のノードkを見つけるための視覚的な解釈が好きなんだ。Xの距離木を葉インデックス0, 1, 2…で作り、各ノードにX^葉インデックスのラベルを付ける。特定のラベルからの距離を示すんだ。 自分が知っているのは、これはSimon TathamのPortable Puzzle Collectionの作者と同じ人なんだ。オフラインで暇なときにぜひ遊んでみてほしい。 そしてPuTTYを書いたのも同じSimon Tathamだよ。 一番のポイントは、マインスイーパのアルゴリズムが、猜測の必要がないゲームを作っていることなんだよ。 最近、カスタムの最適化ソルバー（例えばIsing Machines）がXOR問題でベンチマークを取ってるんだ。ガウス消去で多項式時間で解けるのに、ソルバーは指数関数的なスケーリングを示す。ただのパフォーマンスを測る良い方法だよ。McElieceシステムに関する実装も面白い。 TI-83でZ80アセンブリを学んでたとき、機械語の1バイトが重要だったんだ。aをゼロにするために、’XOR a’を使ってた。これは1バイトの命令だけど、‘LD a, 0’は2バイトも必要なんだよ。 XORスワップの部分を修正するために著者にメールを送ったことがある。ある時、スワップの実装を‘XOR swap’に置き換えたけど、プログラムが壊れたんだ。要するに、同じ場所の値を入れ替えるとバグが出たってこと。 XORはLEETのFizzBuzz回答の一つでも使われているよ。 バイナリの量子化ベクトルでは、類似度は単にXORのポップカウントをビット数で割ることで計算できるんだよね。それをコサイン類似度や距離に変換する方法もあるよ。 XORで描画するのは前の状態を簡単に復元できるからだけじゃないんだ。黒白のディスプレイで矩形をドラッグしてると、填充された部分の上を移動すると見えなくなっちゃう。それがXORなら填充された部分が反転するから、矩形の全体がいつでも見えるんだ。ただし、静的なノイズが表示されてると無理だけどね。 エルミタージュでは、先行技術があったにもかかわらずXORを使った描画に特許を取得した会社があったんだ。その特許でコモドールを訴えることに成功したんだって。この訴訟のコストがコモドールの崩壊に寄与したとも言われているよ。 効率的なアルゴリズムが知りたいな。整数のN x N配列を生成するのに、各エントリーはその列の上や行の左に出ていない最小の整数にする方法は？このスレッドに投稿するのはネタバレかも。 “xor”って聞くだけで90年代のウイルスが自分自身をXOR操作で暗号化したり隠したりしてた頃を思い出すよ。アセンブリコードでレジスタをゼロにすることとか、懐かしい気持ちになるな。 XORはCliffordとCayley-Dickson代数の基本的な要素ごとの乗算なんだ。ただそれらがどう異なるか、各々の特性を持つには符号計算に全てがあるんだよ。 俺はXORをヘテロオペレーターとして覚えてるな。 8ビットコンピュータ（Z80や8086など）では、XOR REG,REGの方がREG←0の操作よりも速いことが多かったんだよ。 日常生活では「または」というと、たいていXORを指すことが多いよね？ だから、あいまいさを避けるために“and/or”って表現がよく使われるんだよ。 データエンジニアとして、最近では二つのデータベース間のSQL方言の違いや、トランザクション分離の問題で行が抜けることがあるんだよね。もっとコメントを表示（1）
それは指摘に同意するよ、言葉遣いを誤ってたみたい。基本的な考え方をいじるのは面白いし、IPv4スペースをメモリにマッピングするのが楽しい。ただ、実際に使えるアドレスは少ないから、少ない計算で翻訳できるように工夫するつもり！
真似っこみたいだけど、実際にポインタの違いを使うのともあまり変わらないんじゃない？
そんなことはないよ。ラップアラウンドを自然に起こさせれば問題ない。必要なのは関数だけだよ。もっとコメントを表示（2）
»> from unicodedata import lookup, name
»> name(chr(ord(lookup(‘AUTOMOBILE’)) ^ 0x20))
’NO PEDESTRIANS’
🚀 → 🏔️
引用してほしい。もっとコメントを表示（3）
＞これらの二つのデータベースには異なるSQLダイアレクトがある。
それに、データをXORして比較する方法を考えてるんだ。整列を気にせずにデータが同じかどうか比べられる方法を見つけられたらいいな。
要するに、Datafoldのdatadiffみたいに、オンプレミスでも動くツールが欲しい。まだ試している最中だけど、整数をXORして何か有用なものが得られる気がする。
