Reversing bits in C

In my day job, we have a device that needs data sent to it with the bits reversed. For example, if we were sending an 8-bit value of 128, that bit pattern is 10000000. The device expects the high bit first so we’d send it 00000001.

In one system, we do an 8-bit bit reversal using a lookup table. I suppose that one needed it to be really fast.

In another (using a faster PIC24 chip with more RAM, flash and CPU speed), we do it with a simple C routine that was easy to understand.

I suppose this breaks down to four main approaches to take:

  • Smallest Code Size – for when ROM/flash is at a premium, even if the code is a confusingf mess.
  • Smallest Memory Usage – for when RAM is at a premium, even if the code is a confusing mess.
  • Fastest – for when speed is the most important thing, even if the code is a confusing mess.
  • Clean Code – easiest to understand and maintain, for when you don’t want code to be a confusing mess.

In our system, which is made up of multiple independent boards with their own CPUs and firmware, we do indeed have some places where code size is most important (because we are out of room), and other places where speed is most important.

When I noticed we did it two different ways, I wondered if there might be even more approaches we could consider.

I did a quick search on “fastest way to reverse bits in C” and found a variety of resources, and wanted to point out this fun one:

At that section of this lengthy article are a number of methods to reverse bits. Two of them make use of systems that support 64-bit math and do it with just one line of C code (though I honestly have no understanding of how they work).

Just in case you ever need to do this, I hope this pointer is useful to you.

Happy reading!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.