## Faster way to reverse the bits in a word

13th August 2024

In my previous post, Six ways to reverse the bits in a word, I compares six different routines to reverse the order of the bits in a 32-bit word. I've been thinking a bit more about this, and have come up with a solution that's slightly faster than any of the routines I gave in that article.

It's perhaps obvious that the holy grail would be a lookup table, consisting of an array of 2^32 elements, giving the reverse of each of the possible bit patterns:

`(defvar a (make-array (expt 2 32)))`

However, apart from being impractical, this doesn't work because the largest array you can create in LispWorks is 134216673 elements.

However, you can combine one of my previous solutions with a small lookup table to achieve an improvement, as follows:

### Recursive, reverse of bottom half followed by reverse of top half, with lookup table

This uses the following recursive algorithm:

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

• If n is 4 look up the result in a 16-element lookup table.
• 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 reversebits7 (b &optional (n 32))
(cond
((= n 4)
(nth
(logand b #b1111)
'(#b0000 #b1000 #b0100 #b1100 #b0010 #b1010 #b0110 #b1110
#b0001 #b1001 #b0101 #b1101 #b0011 #b1011 #b0111 #b1111)))
(t
(setq n (/ n 2))
(logior
(ash (reversebits7 b n) n)
(reversebits7 (ash b (- n)) n)))))```

The execution time of this version is 2.3µs, which beats all the routines in my previous post.