uuuu 第3回に参加しました。今回のテーマは Divide and Conquer (分割統治)の計算オーダーでした。
この種類のアルゴリズムの例として出ていたのが binary search と merge sort でしたが、他に知られているものとして
があります。
アルゴリズムを表現するならやはり 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)))
参考: