Bit Reversal

3^rd June, 2010.

In Embedded Systems Programming, it is often required to reverse bits in the machine word (it can be of any length). Usually in desktop programming we will have high speed processors that operate in the order of few Giga Hz. Where as in embedded systems such as cell phone the core operates in the order of hundreds of Mega Hz. Hence, every byte and every instruction is counted for best optimum algorithm. Note that computing power is not determined by processor speed. We have Param Padma super computer constructed on 630 nodes (processors) operating at low frequency.

It is important to select an optimum algorithm than playing with tricks. Further optimization can be achieved by fine tuning the algorithm implementation. A bit reversal would be required in places such as Fast Fourier Transform in implementing DSP algorithms. Here is algorithm to reverse bits of 32 bit word,

• Swap adjacent bits in the word, i.e. bit position pairs are (0, 1), (2, 3)…(28, 29), (30, 31).
• Swap adjacent 2 bits in the word, i.e. bit position pairs are (01, 23), (45, 67)…
• Swap adjacent 4 bits in the word
• Swap adjacent 8 bits in the word
• Swap adjacent 16 bits in the word

It can be done in log(32) = log(2⁵) = 5 steps. It is analogous to binary search algorithm. Similar technique can be used to count number of 1 bits in the word. Try it.