なぜうまくいくのか?
出典: フリー百科事典『ウィキペディア（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 が残されている。
※この「なぜうまくいくのか?」の解説は、「XOR連結リスト」の解説の一部です。
「なぜうまくいくのか?」を含む「XOR連結リスト」の記事については、「XOR連結リスト」の概要を参照ください。
ウィキペディア小見出し辞書の「なぜうまくいくのか?」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- なぜうまくいくのか?のページへのリンク
