Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C

This is another solution for folks who love recursion.

The idea is simple. Divide up input by half and swap the two halves, continue until it reaches single bit.

Illustrated in the example below.



Ex : If Input is 00101010   ==> Expected output is 01010100



1. Divide the input into 2 halves 

    0010 --- 1010



2. Swap the 2 Halves

    1010     0010



3. Repeat the same for each half.

    10 -- 10 ---  00 -- 10

    10    10      10    00



    1-0 -- 1-0 --- 1-0 -- 0-0

    0 1    0 1     0 1    0 0



Done! Output is 01010100

Here is a recursive function to solve it. (Note I have used unsigned ints, so it can work for inputs up to sizeof(unsigned int)*8 bits.

The recursive function takes 2 parameters - The value whose bits need to be reversed and the number of bits in the value.

int reverse_bits_recursive(unsigned int num, unsigned int numBits)

{

    unsigned int reversedNum;;

    unsigned int mask = 0;



    mask = (0x1 << (numBits/2)) - 1;



    if (numBits == 1) return num;

    reversedNum = reverse_bits_recursive(num >> numBits/2, numBits/2) |

                   reverse_bits_recursive((num & mask), numBits/2) << numBits/2;

    return reversedNum;

}



int main()

{

    unsigned int reversedNum;

    unsigned int num;



    num = 0x55;

    reversedNum = reverse_bits_recursive(num, 8);

    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);



    num = 0xabcd;

    reversedNum = reverse_bits_recursive(num, 16);

    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);



    num = 0x123456;

    reversedNum = reverse_bits_recursive(num, 24);

    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);



    num = 0x11223344;

    reversedNum = reverse_bits_recursive(num,32);

    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

}

This is the output:



Bit Reversal Input = 0x55 Output = 0xaa

Bit Reversal Input = 0xabcd Output = 0xb3d5

Bit Reversal Input = 0x123456 Output = 0x651690

Bit Reversal Input = 0x11223344 Output = 0x22cc4488

4 years ago

Another loop-based solution that exits quickly when the number is low (in C++ for multiple types)

template<class T>

T reverse_bits(T in) {

    T bit = static_cast<T>(1) << (sizeof(T)  8 - 1);

    T out;



    for (out = 0; bit && in; bit >>= 1, in >>= 1) {

        if (in & 1) {

            out |= bit;

        }

    }

    return out;

}

or in C for an unsigned int

unsigned int reverse_bits(unsigned int in) {

    unsigned int bit = 1u << (sizeof(T)  8 - 1);

    unsigned int out;



    for (out = 0; bit && in; bit >>= 1, in >>= 1) {

        if (in & 1)

            out |= bit;

    }

    return out;

}

4 years ago

Native ARM instruction "rbit" can do it with 1 cpu cycle and 1 extra cpu register, impossible to beat.

4 years ago