なぜうまくいくのか?

ウィキペディア小見出し辞書

なぜうまくいくのか?

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/01/23 13:39 UTC 版)

「XOR連結リスト」の記事における「なぜうまくいくのか?」の解説

鍵となるのは、最初の命令と以下のようなXORの性質である。 X⊕X=0 X⊕0=X X⊕Y=Y⊕X (X⊕Y)⊕Z=X⊕(Y⊕Z) R2 レジスタには、現在のノード C のアドレスと1つ前のノードのアドレス P の XOR、すなわち C⊕P が常に格納されている。ノードのリンクフィールドには、前後のノードのアドレスのXOR、すなわち L⊕R が格納されている。従って、R2 (C⊕P) と現在のリンクフィールド (L⊕R) の XOR を求めると C⊕P⊕L⊕R となる。 1つ前のノードが L であった場合、P と L は同じなので打ち消しあい、C⊕R が残る。 1つ前のノードが R であった場合、P と R は同じなので打ち消しあい、C⊕L が残る。 どちらの場合も、残るのは現在のアドレスと次のノードのアドレスの XOR である。これを R1 にある現在ノードのアドレスと XOR することで次のノードのアドレスだけが残る。このとき、R2 には新たな現在ノードと1つ前のノードのアドレスの XOR が残されている。