Subject: Re: bit-reversal in Lisp? From: Erik Naggum <erik@naggum.no> Date: 1998/11/28 Newsgroups: comp.lang.lisp Message-ID: <3121241344668341@naggum.no> * 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?