fixedpoint.jp - Divide and Conquer




Divide and Conquer

uuuu 第3回に参加しました。今回のテーマは Divide and Conquer (分割統治)の計算オーダーでした。

この種類のアルゴリズムの例として出ていたのが binary search と merge sort でしたが、他に知られているものとして

ビットの逆転
1ワード(ここでは4オクテット)中のビットの順序を逆順に入れ替える操作(FFTで利用される)
ビットの population count
1ワード中の立っている(つまり1の)ビットの個数を数える操作

があります。

アルゴリズムを表現するならやはり Scheme ということで、R6RS に従ってやってみます。ビットの逆転を D&C でやるには次のようなコードで実現できます;

(define (rev x)
  (set! x (bitwise-or (bitwise-arithmetic-shift-left (bitwise-and x #x55555555) 1) (bitwise-arithmetic-shift-right (bitwise-and x #xAAAAAAAA) 1)))
  (set! x (bitwise-or (bitwise-arithmetic-shift-left (bitwise-and x #x33333333) 2) (bitwise-arithmetic-shift-right (bitwise-and x #xCCCCCCCC) 2)))
  (set! x (bitwise-or (bitwise-arithmetic-shift-left (bitwise-and x #x0F0F0F0F) 4) (bitwise-arithmetic-shift-right (bitwise-and x #xF0F0F0F0) 4)))
  (set! x (bitwise-or (bitwise-arithmetic-shift-left (bitwise-and x #x00FF00FF) 8) (bitwise-arithmetic-shift-right (bitwise-and x #xFF00FF00) 8)))
  (set! x (bitwise-or (bitwise-arithmetic-shift-left (bitwise-and x #x0000FFFF) 16) (bitwise-arithmetic-shift-right (bitwise-and x #xFFFF0000) 16)))
  x)

ビットの population count を D&C でやるには次のようなコードで実現できます;

(define (pop x)
  (set! x (+ (bitwise-and x #x55555555) (bitwise-and (bitwise-arithmetic-shift-right x 1) #x55555555)))
  (set! x (+ (bitwise-and x #x33333333) (bitwise-and (bitwise-arithmetic-shift-right x 2) #x33333333)))
  (set! x (+ (bitwise-and x #x0F0F0F0F) (bitwise-and (bitwise-arithmetic-shift-right x 4) #x0F0F0F0F)))
  (set! x (+ (bitwise-and x #x00FF00FF) (bitwise-and (bitwise-arithmetic-shift-right x 8) #x00FF00FF)))
  (set! x (+ (bitwise-and x #x0000FFFF) (bitwise-and (bitwise-arithmetic-shift-right x 16) #x0000FFFF)))
  x)

いずれのコードもマシンの論理演算で置き換えることができ分岐が不要です。すっかり忘れていたのですが、これらの計算について「ハッカーのたのしみ」にはっきりと、そしてそれ以上のことが書かれています。

また Gauche でも

(define bitwise-and logand)
(define bitwise-or logior)
(define bitwise-arithmetic-shift-left ash)
(define (bitwise-arithmetic-shift-right x n) (ash x (- n)))
と定義すれば上のコードは動作します。ただし符号ビットが関係する場合にはうまくいきません。

参考:


© 2006-2008 Takeshi Abe