Subject: Re: bit-reversal in Lisp?
From: Erik Naggum <>
Date: 1998/11/28
Newsgroups: comp.lang.lisp
Message-ID: <>

* Louis Glassy <>
| (defun bitrev (n nbits)
|   (let ((r 0))
|     (dotimes  (i nbits r)
|       (when (= (mod n 2) 0)
| 	    (setf r (ash r 1)))
|       (when (= (mod n 2) 1)
| 	    (setf r (1+ (ash r 1))))
|       (setf n (ash n -1)))))

  OK, here's my take on it:

(defun reverse-integer (integer &optional (bits (integer-length integer)))
  (declare (optimize (speed 3) (safety 0)))
  (do* ((n integer (ash n -1))
	(i bits (1- i))
	(r (logand n 1) (+ r r (logand n 1))))
       ((not (plusp i)) r)
    (declare (fixnum n i r))))

  despite the generally braindamaged Intel processor, this compiles to
  pretty tight code with ACL 5.0 for Linux.

  since this function might well be used on bignums or even 32-bit numbers
  that are not directly representable, it might be worth the pain to break
  up a bignum into successive fixnum-size parts and concatenate them back
  into a bignum.  this generalization is left as an exercise to the reader.

  The Microsoft Dating Program -- where do you want to crash tonight?