Efficient Algorithms for Bit Reversal in C

Introduction

Bit reversal is a fundamental operation in computer science, commonly used in cryptography, signal processing, and data compression. It involves completely reversing the order of bits in a binary number, for instance, converting 0010 0000 to 0000 0100. This is distinct from endianness swapping, which only rearranges bytes.

Algorithm Methods

Several algorithms exist for bit reversal, each with trade-offs in memory usage and execution speed. Key approaches include bitwise operations, lookup tables, and simple loops.

Bitwise Operation Method

The bitwise operation method employs a divide-and-conquer strategy to reverse bits in logarithmic time, making it memory-efficient.

unsigned int reverse_bits(register unsigned int x) {
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return ((x >> 16) | (x << 16));
}

This code swaps adjacent bits, then pairs of bits, followed by groups of four bits, and finally handles bytes and 16-bit halves. It is optimized for 32-bit integers.

Lookup Table Method

The lookup table method uses a precomputed table for fast bit reversal, offering high speed at the cost of additional memory.

static const unsigned char BitReverseTable256[] = {
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
  0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
  0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
  0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
  0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
  0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
  0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
  0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
  0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
  0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

unsigned int reverse_with_table(unsigned int v) {
    return (BitReverseTable256[v & 0xff] << 24) |
           (BitReverseTable256[(v >> 8) & 0xff] << 16) |
           (BitReverseTable256[(v >> 16) & 0xff] << 8) |
           (BitReverseTable256[(v >> 24) & 0xff]);
}

This method decomposes the 32-bit integer into four bytes, reverses each using the table, and reassembles them. Benchmarks show it processes 100 million integers in approximately 0.63 seconds under O2 optimization.

Simple Loop Method

The simple loop method iterates through each bit to build the reversed value, making it easy to comprehend but less efficient.

unsigned int reverse_simple(unsigned int v) {
    unsigned int r = v & 1;
    int s = sizeof(v) * CHAR_BIT - 1;
    for (v >>= 1; v; v >>= 1) {
        r <<= 1;
        r |= v & 1;
        s--;
    }
    r <<= s;
    return r;
}

Starting from the least significant bit, this approach constructs the result incrementally, suitable for educational purposes.

Performance Analysis

Benchmark tests on a Core 2 Duo processor indicate that the lookup table method (option 1) is the fastest, averaging 0.63 seconds for 100 million reversals under O2 optimization. The bitwise operation method follows at about 0.89 seconds, while the simple loop is slower. Memory-wise, the lookup table uses 256 bytes, whereas bitwise operations have minimal overhead.

Conclusion

For high-performance applications, the lookup table method is recommended; if memory is constrained, the bitwise operation method offers a good balance. Developers should choose based on specific requirements for speed and resource usage.