About me

About me

Feeds

RSS feed

Six ways to reverse the bits in a word

29th June 2024

What's the best way to reverse the order of the bits in a 32-bit word using Lisp? There's no obviously best way to do this, so I thought I'd compare the alternatives, using LispWorks on a Mac.

In the following functions b is the bitstring to be reversed, n is the length of the bitstring, and r is the reversed result.

To measure the execution time of each version I ran:

(time
 (let (r)
   (format t "~b~%"
           (dotimes (x 1000000 r)
             (setq r (reversebits #b10110011100011110000111110000011 32))))))

Iterate, starting from the bottom bit

Here's the most obvious approach. Iterate around 32 times, shifting the bottom bit out from the bitstring and shifting it in to the bottom of the result:

(defun reversebits1 (b &optional (n 32))
  (let ((r 0))
    (dotimes (x n r)
      (setq r (logior (ash r 1) (logand b 1))
            b (ash b -1)))))

The execution time of this version is 2.6µs.

Iterate, starting from the top bit

Alternatively, we can iterate with x from 0 to 31, shifting the (31-x)th bit from the bitstring down to position x in the result:

(defun reversebits2 (b &optional (n 32))
  (let ((r 0))
    (dotimes (x n r)
      (setq r (logior r (ash (logand (ash b (- x 31)) 1) x))))))

The execution time of this version is 3.0µs.

Using do

Here's a version using do:

(defun reversebits3 (b &optional (n 32))
  (do ((x 0 (1+ x))
       (r 0 (logior (ash r 1) (logand i 1)))
       (i b (ash i -1)))
      ((= x n) r))) 

The execution time of this version is 2.7µs.

Recursive, reverse of bottom bits followed by top bit

Here's a recursive version using the following algorithm:

To reverse n bits:

  • If n is 1 the result is just the bit.
  • Otherwise the result is the reverse of the bottom (n-1) bits followed by the (n-1)th bit.

Here's the function:

(defun reversebits4 (b &optional (n 32))
  (cond
   ((= n 1) b)
   (t (decf n)
      (logior (ash (reversebits4 b n) 1) (logand (ash b (- n)) 1)))))

The execution time of this version is 5.7µs.

Recursive, reverse of bottom half followed by reverse of top half

This is my favourite solution. It uses the following recursive algorithm:

To reverse n bits (n must be a power of 2):

  • If n is 1 the result is just the bit.
  • Otherwise the result is the reverse of the bottom (n/2) bits followed by the reverse of the top (n/2) bits.

Here's the function:

(defun reversebits5 (b &optional (n 32))
  (cond
   ((= n 1) (logand b 1))
   (t
    (setq n (/ n 2))
    (logior
     (ash (reversebits5 b n) n)
     (reversebits5 (ash b (- n)) n)))))

The execution time of this version is 3.6µs.

Single pass version

Finally, a single-pass version using bit masks and shifts [1]. It works as follows:

  • Swap odd and even bits.
  • Swap adjacent pairs of bits.
  • Swap adjacent 4-bit nibbles.
  • Reverse order of 8-bit bytes.
Here's the function:
(defun reversebits6 (b &optional (n 32))
  (setq b (logior (ash (logand b #x55555555) 1) (logand (ash b -1) #x55555555)))
  (setq b (logior (ash (logand b #x33333333) 2) (logand (ash b -2) #x33333333)))
  (setq b (logior (ash (logand b #x0f0f0f0f) 4) (logand (ash b -4) #x0f0f0f0f)))
  (setq b (logior (ash b 24) (ash (logand b #xff00) 8) 
                  (logand (ash b -8) #xff00) (logand (ash b -24) #xff))))

The execution time of this version is 2.4µs; the fastest but least understandable!

Other ideas

I'd welcome any other suggestions using techniques I haven't thought of.

  1. ^ From "Hacker's Delight" by Henry S. Warren, Jr., page 129.

Next: Faster way to reverse the bits in a word

Previous: Predicates that don't return 't'

blog comments powered by Disqus