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

blog comments powered by Disqus