列挙

2^n個の数字を列挙する場合、(1<<n)回ループすればよい。このとき、なるべくビットの変更が最小になるようにしたいとしよう。

実は、簡単な法則で、変更は常に1ビットすむ。言葉を替えると、n次元単体の辺を周る一筆書きが存在する。 16個でやってみると、列挙は、0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8であり、このとき、変更されるビットは、1,2,1,4,1,2,1,8,1,2,1,4,1,2,1である。2回おきに1が、4回おきに2が、8回おきに4が、16回おきに8が、以降も同様に現れる。

ここで、問題

i 番目に対して、変更されるビットを返す関数を作成せよ。

できただろうか。ヒント：関数内は20文字でできる。

答えは、return(i|~(~i-1))-i;である。（もっと、短くなるかもしれない。）