A recursive count leading zeroes algorithm for bitvectors in Lisp.

clzt.lisp

(defun b2int (bitvector)
  "Convert a binary string into an integer."
  (reduce #'(lambda (first second)
	      (+ (* 2 first) second))
	  bitvector))

(defun concat-bits (b1 b2)
  "Convenience function to concatenate bit vectors."
  (concatenate 'bit-vector b1 b2))

(defun combine-clzt-halfs (left right)
  "Combine the values of the two clzt halfs. If left is saturated,
   zeroes on the right continue and need to be added;
   otherwise just keep left"
  (let ((top-bits (list (bit left 0) (bit right 0))))
    (cond
      ((equal top-bits '(1 1))
       (concat-bits left #*0))

      ((equal top-bits '(1 0))
       (concat-bits #*01 (subseq right 1)))

      ((or (equal top-bits '(0 0))
	   (equal top-bits '(0 1)))
       (concat-bits #*0 left)))))

(defun clzt-pow2 (x)
  "Count leading zeroes of given bitvector, which must be a
   power of two length"
  (let ((len (length x))
	(half-len (/ (length x) 2)))
    (cond ((eq len 1) (bit-not x))
	  (t (combine-clzt-halfs
	      (clzt-pow2 (subseq x 0 half-len))
	      (clzt-pow2 (subseq x half-len len)))))))

(defun create-mask (n)
  "Create a bitmask with n bits"
  (make-sequence '(vector bit) n :initial-element 1))

(defun clog2 (x)
  "Return number of bits needed to represent number"
  (round (fceiling (log x 2))))

(defun next-pow2 (x)
  "Given a number return the next power of 2 this number this fits into"
  (expt 2 (clog2 x)))

(defun clzt (x)
  "Given bitvector x, return leading zeros.
   Unlike clzt-pow2, this works for arbitrary bit-widths."
  ;; Expand to next power of two by appending a bit-mask with missing bits.
  (let ((bits-to-next-power-2 (- (next-pow2 (length x))
				 (length x))))
    (clzt-pow2 (concat-bits x (create-mask bits-to-next-power-2)))))

To test, run, e.g.:

 (clzt #*000100)

This returns the number in bits as a binary vector (#*0011); use the b2int (also defined above) to convert that to an integer

 (b2int (clzt #*000100))

... returning 3.