ビットごとの秘法と技法 から

TAOCPの演習問題7.1.3-20にGosperのハックというのがある.

正の整数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=α01^a0^b

とする. つまりxは左に適当な0と1の列αがあり, その右に0が1個, その右に1がa >0, その右に0がb ≥0個あるとする.

uの式は有名な最も右の1を取り出すものだから

u=10^b

である.

v=x + uは1の並びの右端に1を足すから

v=α10^a0^b.

x ⊕ v は左のαがキャンセルされるから

x ⊕ v=11^a0^b

になり, これをuで割るから右の0の列が消えて

(x ⊕ v)/u=11^a

つまり1が右端にa +1個ならぶ. これを2ビット右シフトするから右端に1がa -1個ならぶ. これをvに足すから

y = α10^b01^a-1     (a >0に注意)

で次のyが得られたのであった. たしかにハックだね. これはMITのHAKMEMの175番にある.