The following Common Lisp functions should be reasonably efficient if they didn't have to recurse down to the individual bit. But even without a better function for reversing a whole word, "memoizing" int-bit-rev-helper would help a lot, by building up a table of bit-reversed smaller integers. (defun int-bit-rev (n) ;;; This definition makes a slight pretense at efficiency. ;;; Reverse the bits of a bignum n. (if (minusp n) (- (int-bit-rev (- n))) (let* ((nlobits (1- (integer-length (logand n (- n)))))) (ash (int-bit-rev-helper (ash n (- nlobits)) (- (integer-length n) nlobits)) nlobits)))) (defun int-bit-rev-helper (n k) ;;; Reverse the bits of an odd bignum n with k "significant" bits. ;;; Split the number in the middle, then bit-reverse each half. ;;; For better efficiency call an intrinsic function for k<33. ;;; Would work a lot better with memoization. (if (< k 2) n (let* ((lolen (ash k -1)) (hilen (- k lolen)) (lomask (1- (ash 1 lolen))) (lopart (logand n lomask)) (hipart (ash n (- lolen))) (revlopart (int-bit-rev-helper lopart lolen)) (revhipart (int-bit-rev-helper hipart hilen))) (logior (ash revlopart hilen) revhipart))))