;; it's only 4 "real" lines if you strip off the declarations ;; plus the data. I haven't done any timings.
(defvar ctzmap(make-array 37 :element-type 'fixnum :initial-contents '(32 0 1 26 2 23 27 0 3 16 24 30 28 11 0 13 4 7 17 0 25 22 31 15 29 10 12 6 0 21 14 9 5 20 8 19 18)))
;; if z is too big, just look at the trailing 32 bits.. if they're all zero, ;; shift z and ;; keep looking
(defun ctz(z) ;; works in blocks of 32 bits
(declare (integer z)
(type (simple-array fixnum 37) ctzmap)
(optimize (speed 3) (safety 0)))
(let* ((zz (logand z #.(1-(expt 2 32) )))
(sofar(aref ctzmap (the fixnum (mod (logand zz (- zz)) 37)))))
(declare (integer zz) (fixnum sofar))
(if (= sofar 32) (+ sofar (the fixnum (ctz (ash z -32)))) sofar))))
Cheers
Richard Fateman [email protected]. ask if you want more than 2000 chars.
(UC Berkeley, retired CS Professor)