XORを使用したリスト - longicornの日記

XORを使用したリストがあるらしい。
検索したけど、日本語サイトでは解説が無いのでメモ
性能は普通のよりも、速度、データ量で上回る。

通常の構造体は以下の様な感じ

typedef struct node {
   struct node *prev;
   struct node *next;
   int data;
} node;

xor版は以下の様になる。

typedef struct node {
   struct node *diff;
   int data;
} node;

ソースを見て理解した範囲だと以下のような感じ？
構造体に保存するのは2つのアドレスのXORの結果となる。
現在のアドレスを知るには1つ前のアドレスと保存しているXORの値をANDすればいい。

早いんだろうけど、実装を考えるとバグが出そうなのでよっぽどの場合でもない限り使わなさそう。
ただ、メモリがきつい場合にはいいかも。