Count trailing zeros, revisited

4 points

11 years ago

I don't know if this is old and silly, but I came across common lisp code (here) to count trailing zeroes, an application I actually needed. ;; mysterious program depends on value of 2^n mod 37.. since 37 is ;; relatively prime to 2^n for n=0 to 32. ;; reference https://graphics.stanford.edu/~seander/bithacks.html

;; 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)

1 comment