Bit reversal of an integer, ignoring integer size and endianness

Question :

Bit reversal of an integer, ignoring integer size and endianness,

Answer :

Given an integer typedef:

typedef unsigned int TYPE;  

or

typedef unsigned long TYPE;  

I have the following code to reverse the bits of an integer:

TYPE max_bit= (TYPE)-1;    void reverse_int_setup()  {      TYPE bits= (TYPE)max_bit;        while (bits <<= 1)          max_bit= bits;  }    TYPE reverse_int(TYPE arg)  {      TYPE    bit_setter= 1, bit_tester= max_bit, result= 0;        for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1)          if (arg & bit_tester)              result|= bit_setter;      return result;  }  

One just needs first to run reverse_int_setup(), which stores an integer with the highest bit turned on, then any call to reverse_int(arg) returns arg with its bits reversed (to be used as a key to a binary tree, taken from an increasing counter, but that’s more or less irrelevant).

Is there a platform-agnostic way to have in compile-time the correct value for max_int after the call to reverse_int_setup(); Otherwise, is there an algorithm you consider better/leaner than the one I have for reverse_int()?

Thanks.

,

#include  #include    #define TYPE_BITS sizeof(TYPE)*CHAR_BIT    typedef unsigned long TYPE;    TYPE reverser(TYPE n)  {      TYPE nrev = 0, i, bit1, bit2;      int count;        for(i = 0; i < TYPE_BITS; i += 2)      {          /*In each iteration, we  swap one bit on the 'right half'           of the number with another on the left half*/            count = TYPE_BITS - i - 1;  /*this is used to find how many positions                                       to the left (and right) we gotta move                                       the bits in this iteration*/            bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/          bit1 <<= count;         /*Shift it to where it belongs*/            bit2 = n & 1<<((i/2) + count);  /*Find the 'left half' bit*/          bit2 >>= count;         /*Place that bit in bit1's original position*/            nrev |= bit1;   /*Now add the bits to the reversal result*/          nrev |= bit2;      }      return nrev;  }    int main()  {      TYPE n = 6;        printf("%lu", reverser(n));      return 0;  }  

This time I’ve used the ‘number of bits’ idea from TK, but made it somewhat more portable by not assuming a byte contains 8 bits and instead using the CHAR_BIT macro. The code is more efficient now (with the inner for loop removed). I hope the code is also slightly less cryptic this time. 🙂

The need for using count is that the number of positions by which we have to shift a bit varies in each iteration – we have to move the rightmost bit by 31 positions (assuming 32 bit number), the second rightmost bit by 29 positions and so on. Hence count must decrease with each iteration as i increases.

Hope that bit of info proves helpful in understanding the code…

That's the answer Bit reversal of an integer, ignoring integer size and endianness, Hope this helps those looking for an answer. Then we suggest to do a search for the next question and find the answer only on our site.

Disclaimer :

The answers provided above are only to be used to guide the learning process. The questions above are open-ended questions, meaning that many answers are not fixed as above. I hope this article can be useful, Thank you

Read More  What common web exploits should I know about?