正の整数xについて
u ← x&-x;
v ← x + u;
y ← v + (((x⊕v)) »2);
としてyを返す.
とにかくやってみよう.
(define (gosper x) (let* ((u (band x (- (expt 2 16) x))) (v (+ x u)) (y (+ v (>> (/ (bxor v x) u) 2)))) y)) (gosper 1) => 2 (gosper 2) => 4 (gosper 4) => 8 (gosper 8) => 16 (gosper 3) => 5 (gosper 5) => 6 (gosper 6) => 9 (gosper 7) => 11 (gosper 11) => 13という次第で, 1のビットの数が同じの次に大きい整数が得られる.
その理由を考えてみた.
x=α01a0b
とする. つまりxは左に適当な0と1の列αがあり, その右に0が1個, その右に1がa >0, その右に0がb ≥0個あるとする.
uの式は有名な最も右の1を取り出すものだから
u=10b
である.
v=x + uは1の並びの右端に1を足すから
v=α10a0b.
x ⊕ v は左のαがキャンセルされるから
x ⊕ v=11a0b
になり, これをuで割るから右の0の列が消えて
(x ⊕ v)/u=11a
つまり1が右端にa +1個ならぶ. これを2ビット右シフトするから右端に1がa -1個ならぶ. これをvに足すから
y = α10b01a-1 (a >0に注意)
で次のyが得られたのであった. たしかにハックだね. これはMITのHAKMEMの175番にある.
0 件のコメント:
コメントを投稿