About me

About me

Feeds

RSS feed

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