From: Louis Glassy
Subject: bit-reversal in Lisp?
Date: 
Message-ID: <73i311$h7d$1@netra.msu.montana.edu>
While recoding the "Numerical Recipes in C" routine FOUR1
(1-D complex FFT) in Common Lisp (or whatever Lisp is 
implemented by gcl-2.2.2), I needed to be able to reverse 
the bits in a number, to make the output values go into 
the right places in the output vector.

By "bit reversal", I mean: take the bits of a positive integer,
reverse the bit pattern (left-padding with zeros to get the 
right total number of bits, which you know ahead of time), and 
out pops the bit-reversed value, another positive integer.

E.g., #10r10 -> #2r1010 -> #2r0101 -> #10r5, given 4 bits, and 
      #10r1 -> #2r0001 -> #2r1000 -> #10r8, given 4 bits.

So here's a routine to do it...

;;; bit reverser in lisp.

(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)))))

& it seems to work all right.  I haven't tested it exhaustively,
but I suspect it's correct and fast enough for what I want it for.

My question for you is about style: how would *you* do this 
sort of bit-reversal task, assuming you have all or anything 
in CL to help you?  In other words, what's the "Lispy" way to solve
this problem, a way an experienced Lisp programmer would use?

The previous little function is more-or-less a literal translation
of how I'd do this in Fortran [*], and I'm curious if Lisp offers some
slick tools to do this conversion in a cleaner way, something like

	(bits-to-number 
	   (reverse (number-to-bits N nbits))
	   nbits)

??

Thanks kindly,

Lou.

[*] Disclaimer.  I had a Model 23 duplicating punch dropped on 
                 my head as a child, so yes, I often think in 
		 Fortran, even when I code in something else...

-- 
Louis Glassy (······@cs.montana.edu)
Department of Computer Science
Montana State University
Bozeman, Montana 59717 USA

From: Rainer Joswig
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <joswig-2611980136080001@194.163.195.67>
In article <············@netra.msu.montana.edu>, Louis Glassy
<······@acheta.nervana.montana.edu> wrote:

> ;;; bit reverser in lisp.
> 
> (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)))))
> 

Rewrite of your code:

(defun bitrev (n &optional (nbits (integer-length n)))
  (loop for i fixnum from 0 below nbits
        for r integer = (ldb (byte 1 0) n)
                   then (if (logbitp i n)
                           (1+ (ash r 1))
                           (ash r 1))
        finally (return r)))

Using DBP:
(defun bitrev1 (n &optional (nbits (integer-length n)))
  (let ((result 0))
    (loop for i fixnum from 0 below nbits
          for j fixnum downfrom (1- nbits)
          when (logbitp j n)
          do (setf result (dpb 1 (byte 1 i) result)))
    result))

>  I haven't tested it exhaustively,

same for me  ;-)

Or you can work with bit-vectors.

-- 
http://www.lavielle.com/~joswig
From: Arthur Lemmens
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <365D1F6C.768405DD@simplex.nl>
Here's a version that uses a standard trick for reversing vectors.
The trick is to swap elements, starting from the left
and right ends and moving to the middle.

(defun bit-reverse (n &optional (nbits (integer-length n)))
  (dotimes (i (ash nbits -1))
     (rotatef (ldb (byte 1 i) n) 
              (ldb (byte 1 (- nbits i 1)) n)))
  n)

;;;;;;;;;;;;;;;;;;;

CL-USER 75 > (setf *print-base* 2)
10

CL-USER 76 > (bit-reverse #b1)
1

CL-USER 79 > (bit-reverse #b011)
11

CL-USER 80 > (bit-reverse #b011 3)
110

CL-USER 81 > (bit-reverse #b111100001)
100001111

;;;;;;;;;;;;;;;;

> I'm curious if Lisp offers some
> slick tools to do this conversion in a cleaner way

If you were using bit vectors, you could just use reverse.

CL-USER 82 > (reverse #*111100001)

#*100001111
From: Kelly Murray
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <365F09E1.36633E38@IntelliMarket.Com>
Louis Glassy wrote:
> By "bit reversal", I mean: take the bits of a positive integer,
> reverse the bit pattern (left-padding with zeros to get the
> right total number of bits, which you know ahead of time), and
> out pops the bit-reversed value, another positive integer.
>..
> My question for you is about style: how would *you* do this
> sort of bit-reversal task, assuming you have all or anything
> in CL to help you?  In other words, what's the "Lispy" way to solve
> this problem, a way an experienced Lisp programmer would use?
> 

Here's my take on this problem  ;) --kelly murray

---
The "Lispy" way to solve the problem, as you'd probably learn
in a sophmore languages class, is to use recursion:

(defun bit-reverse-lispy (n width)
  (cond
   ((zerop width) 0)
   (t
    (logior
     (ash (ldb (byte 1 0) n) (- width 1))
     (bit-reverse-lispy (ash n -1) (- width 1)) 
     ))))


The "fewest characters" CL library way to solve the problem 
might be:
(defun bit-reverse-dirty-not-quick (n width)
 (parse-integer
  (reverse (format nil "~B" (ldb (byte width 0) n))
  :radix 2)) 

The "real" way to solve the problem is using a loop:

(defun bit-reverse-1 (n width)
  (loop with r = 0
	for i from 0 below width
	for bit = (ldb (byte 1 i) n)
	finally (return r)
      do
      (setf r (logior r (ash bit (- width i 1))))))
      
The "Lisp Pro" way to solve the problem (if warranted) is to 
make it very efficient by using table lookup,
and using macros to essentially
do all the hard work at compile-time:

(defun make-rbit-table ()
  (loop with table = (make-array 256 :element-type '(unsigned-byte 8))
	for i from 0 below 256
	finally (return table)
      do
      (setf (aref table i) (bit-reverse-1 i 8))))

(defun bit-reverse-8 (n width table)
  (loop with r = 0
	for i from 0 below width by 8
	for bits = (aref table (ldb (byte 8 i) n))
	finally (return r)
      do
      (setf r (logior r (ash bits (- width i 8))))))

(defmacro bit-reverse-optimized (n width)
  (loop for i from 0 below 8
	with conds = nil
	finally
	(return
	  `(let ((table ',(make-rbit-table)))
	   (cond
	    ((< ,width 9)
	     (let ((rbit8 (aref table (ldb (byte 8 0) ,n))))
		  (declare (fixnum rbit8))
	        (cond
		 ((eq width 8) rbit8)
		 ,@conds)))
	    (t (bit-reverse-8 ,n ,width table)))))
      do
      (push
       `((eq ,width ,i)
	 (ash rbit8 ,(- (- 8 i))))
       conds)))


(defun bit-reverse (n width)
 (bit-reverse-optimized n width)
 )
From: Erik Naggum
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <3121241344668341@naggum.no>
* Louis 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?
From: Frank Brickle
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <F3512G.oq@news2.new-york.net>
Erik Naggum (····@naggum.no) wrote:

:   OK, here's my take on it:

: ...

:   ...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.

Sorry if this has come up already -- I came to this discussion late --
but if you're going to do that, why not do the lowest-level reversal
as a table lookup? After all, the 2^8 table is only 256 long :-)
Pick your own lowest-level width to suit...
From: Juanma Barranquero
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <36648b19.1112465751@talia.ibernet.es>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sun, 29 Nov 1998 18:04:58 GMT, ·····@lander.es (Juanma Barranquero)
wrote:

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

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

works and it's more similar to the original.

                                                       /L/e/k/t/u


-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i; see <http://www.pgpi.com>

iQA/AwUBNmJ+K/4C0a0jUw5YEQL+pQCfZw7J1O/G8wb4UMRJduN1ZGIsPn0An3WH
vOKXt//+/PgIujVmmvFVEBJU
=/GOg
-----END PGP SIGNATURE-----
From: Buller, Jonathan (EXCHANGE:RICH6:2B81)
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <3662F99B.AFE2279A@nortel.com>
Louis Glassy wrote:
> 
> While recoding the "Numerical Recipes in C" routine FOUR1
> (1-D complex FFT) in Common Lisp (or whatever Lisp is
> implemented by gcl-2.2.2), I needed to be able to reverse
> the bits in a number, to make the output values go into
> the right places in the output vector.

[ Lots of bitreversal specific stuff deleted ]

Have you realized that, for an FFT, you may not want or need
to have (defun bitrev (n nbits) ...) but you might want
(defun bitrevinc (n nbits) ...) instead?

I recently did an FFT in Scheme (please no flames right now... 8-)
I wrote the following:

(define (bit-reversed-increment num size)
  (let loop ((test (arithmetic-shift size -1))
             (mask (arithmetic-shift size -1)))
    (if (zero? (bitwise-and test num))
      (bitwise-xor num mask)
      (let ((tmp (arithmetic-shift test -1)))
        (loop tmp (bitwise-ior mask tmp))))))

You don't waste time reversing most of the bits in the number, you
just need to find the first (non-leading) zero bit, then reverse it
and all the leading bits in front of it.  Then you can write
something like:

(define (bit-reverse-vector! v)
  (let loop ((forward 0) (backward 0))
    (if (= forward (vector-length v))
      v
      (begin
        (if (< forward backward)
           (let ((swap (vector-ref v backward)))
             (vector-set! v backward (vector-ref v forward))
             (vector-set! v forward swap)))
        (loop (+ forward 1) (bit-reversed-increment backward
                                                    (vector-length
v)))))))

This makes the vector shuffling O(n) instead of o(n * lg n) since
the bit reversed increment is amortized O(1) and the walk through
the vector is O(n) whereas the full bit reversal will be O(lg n)
instead, since you are reversing lg n bits.

Jon Buller
(Working on translating a semi-working knowlege of Scheme into a
fully working knowlege of CL, but still in the starting stages.)
From: Gilbert Baumann
Subject: Re: bit-reversal in Lisp?
Date: 
Message-ID: <ywbfsoeu9x4a.fsf@rz114s1.rz.uni-karlsruhe.de>
Well, I am a bit late with my code, but couldn't resist.

(defun 2**k-bit-reverse (k x)
  ;; Reverses the (expt 2 k) bit integer x bitwise
  (do* ((j (ash 1 (1- k)) (ash j -1))
        (m (dpb -1 (byte j j) 0) (logxor m (ash m (- j)))) )
      ((= m 0) x)
    (setf x (logior (ash (logand x m) (- j))
                    (ash (logand x (ash m (- j))) j)))))

You see what is going on, if you look at the hand-coded 16bit version:

(defun 16bit-reverse (x)
  (setf x (logior (ash (logand x #b1111111100000000) -8) 
                  (ash (logand x #b0000000011111111) +8)))
  (setf x (logior (ash (logand x #b1111000011110000) -4) 
                  (ash (logand x #b0000111100001111) +4)))
  (setf x (logior (ash (logand x #b1100110011001100) -2) 
                  (ash (logand x #b0011001100110011) +2)))
  (setf x (logior (ash (logand x #b1010101010101010) -1) 
                  (ash (logand x #b0101010101010101) +1))) )

Gilbert.

-- 
;;; You know you have hacked Lisp too much, when you m-c-x in a C buffer.