N xor [N/2]で隣り合う数のハミング距離が1のbit列が出来るわけ

はじめに

みなさん、ハミング距離は知っていますか？
二つの数のハミング距離というのは二つの数を二進数表記した時、何bit異なるかを指します(間違ってたらごめんなさい)。
例えば、$${12}$$と$${45}$$なら$${1100_{(2)}}$$と$${101101_{(2)}}$$でハミング距離$${2}$$です。
さて、ここで隣り合う数のハミング距離が1のbit列を作る方法として$${N}$$番目の数を$${N\ \text{xor}\ [\frac{N}{2}]}$$とするというものがあるのですが、あまり自明ではありません。
そのため今回解説を書きました。
* []は小数点以下切り捨てを指します。

証明

数学的帰納法を用いて示します。

1 bitの時

$${0\ \text{xor}\ 0 = 0}$$
$${1\ \text{xor}\ 0 = 1}$$
明らかに成立

k bitで成り立つことを仮定

$${0\dots2^k-1}$$について成立しているとします。

k+1 bitで成り立つことを証明

現在
$${0\ \text{xor}\ 0 }$$
……
$${i\ \text{xor}\ [\frac{i}{2}]}$$
……
$${2^k -1\ \text{xor}\ 2^{(k-1)}-1 }$$
が$${k}$$ bitのbit列として成立しています。

以降
$${2^k+i\ \text{xor}\ 2^{k-1}+[\frac{i}{2}] (i=0\dots 2^k -1)}$$
となるわけですが、これを上手くわけます。
$${2^k\ \text{xor}\ i\ \text{xor}\ 2^{k-1} + [\frac{i}{2}]}$$
同じxorを$${2}$$回行うと元に戻るので
$${2^k\ \text{xor}\ (i\ \text{xor}\ 2^k -1)\ \text{xor}\ (2^{k-1} + [\frac{i}{2}] \ \text{xor}\ 2^k -1)}$$
$${i=0\dots 2^k -1}$$と$${2^k -1}$$が$${k}$$bitが立っていることから一部のxorがただの引き算になって
$${2^k\ \text{xor}\ (2^k - i - 1)\ \text{xor}\ (2^{k-1} - [\frac{i}{2}] -1)}$$
$${j=2^k -1 -i}$$とすると
$${2^k\ \text{xor}\ j\ \text{xor}\ [\frac{j}{2}]}$$
これは$${k}$$ bitのものを逆に並べて$${2^k}$$のbitを立てただけのものです。
このため仮定から$${k+1}$$ bitでも成立します。

なんかGray Codeって呼ばれてるらしい

こうやって構成されたハミング距離$${1}$$のbit列のことをGray Codeっていうらしい。