From ...
From: Erik Naggum <erik@naggum.no>
Subject: Re: bit-reversal in Lisp?
Date: 1998/11/28
Message-ID: <3121241344668341@naggum.no>#1/1
X-Deja-AN: 416467030
References: <73i311$h7d$1@netra.msu.montana.edu>
mail-copies-to: never
Organization: Naggum Software; +47 8800 8879; http://www.naggum.no
Newsgroups: comp.lang.lisp

* Louis Glassy <glassy@acheta.nervana.montana.edu>
| (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.

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