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