[math-fun] Recursive integer_bit_reverse function
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))))
While stipulating again that I think "reverse" or "reflect" might best be defined differently: Perhaps http://www.hackersdelight.org/ might have something useful to suggest for implementation hacks? Also, as Henry reminds us, reversing odd positive integers doesn't entail nearly as much definitional angst--it's wagging those infinite tails that's discomfiting. We might, therefore, study the operation n>=0 --> (reverse(2n+1)-1)/2 and something analogous for n<0. Similarly, we might further explore the variation wherein you leave the MSB alone, and just reverse the other bits. I may have submitted some such sequences to the OEIS a while back, I forget.
participants (2)
-
Henry Baker -
Marc LeBrun