Vfrdtyky

This should work:

unsigned char reverse(unsigned char b) {

   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;

   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;

   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;

   return b;

}

First the left four bits are swapped with the right four bits. Then all adjacent pairs are swapped and then all adjacent single bits. This results in a reversed order.

I think a lookup table has to be one of the simplest methods. However, you don't need a full lookup table.

//Index 1==0b0001 => 0b1000

//Index 7==0b0111 => 0b1110

//etc

static unsigned char lookup[16] = {

0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,

0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, };



uint8_t reverse(uint8_t n) {

   // Reverse the top and bottom nibble then swap them.

   return (lookup[n&0b1111] << 4) | lookup[n>>4];

}



// Detailed breakdown of the math

//  + lookup reverse of bottom nibble

//  |       + grab bottom nibble

//  |       |        + move bottom result into top nibble

//  |       |        |     + combine the bottom and top results 

//  |       |        |     | + lookup reverse of top nibble

//  |       |        |     | |       + grab top nibble

//  V       V        V     V V       V

// (lookup[n&0b1111] << 4) | lookup[n>>4]

This fairly simple to code and verify visually.

Ultimately this might even be faster than a full table. The bit arith is cheap and the table easily fits on a cache line.

See the bit twiddling hacks for many solutions. Copypasting from there is obviously simple to implement. =)

For example (on a 32-bit CPU):

uint8_t b = byte_to_reverse;

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

If by “simple to implement” one means something that can be done without a reference in an exam or job interview, then the safest bet is probably the inefficient copying of bits one by one into another variable in reverse order (already shown in other answers).

Since nobody posted a complete table lookup solution, here is mine:

unsigned char reverse_byte(unsigned char x)

{

    static const unsigned char table = {

        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,

    };

    return table[x];

}

template <typename T>

T reverse(T n, size_t b = sizeof(T) * CHAR_BIT)

{

    assert(b <= std::numeric_limits<T>::digits);



    T rv = 0;



    for (size_t i = 0; i < b; ++i, n >>= 1) {

        rv = (rv << 1) | (n & 0x01);

    }



    return rv;

}

EDIT:

Converted it to a template with the optional bitcount

Two lines:

for(i=0;i<8;i++)

     reversed |= ((original>>i) & 0b1)<<(7-i);

or in case you have issues with the "0b1" part:

for(i=0;i<8;i++)

     reversed |= ((original>>i) & 1)<<(7-i);

"original" is the byte you want to reverse.
"reversed" is the result, initialized to 0.

Although probably not portable, I would use assembly language.

Many assembly languages have instructions to rotate a bit into the carry flag and to rotate the carry flag into the word (or byte).

The algorithm is:

for each bit in the data type:

  rotate bit into carry flag

  rotate carry flag into destination.

end-for

The high level language code for this is much more complicated, because C and C++ do not support rotating to carry and rotating from carry. The carry flag has to modeled.

Edit: Assembly language for example

;  Enter with value to reverse in R0.

;  Assume 8 bits per byte and byte is the native processor type.

   LODI, R2  8       ; Set up the bit counter

Loop:

   RRC, R0           ; Rotate R0 right into the carry bit.

   RLC, R1           ; Rotate R1 left, then append carry bit.

   DJNZ, R2  Loop    ; Decrement R2 and jump if non-zero to "loop"

   LODR, R0  R1      ; Move result into R0.

The simplest way is probably to iterate over the bit positions in a loop:

unsigned char reverse(unsigned char c) {

   int shift;

   unsigned char result = 0;

   for (shift = 0; shift < CHAR_BIT; shift++) {

      if (c & (0x01 << shift))

         result |= (0x80 >> shift);

   }

   return result;

}

I find the following solution simpler than the other bit fiddling algorithms I've seen in here.

unsigned char reverse_byte(char a)

{



  return ((a & 0x1)  << 7) | ((a & 0x2)  << 5) |

         ((a & 0x4)  << 3) | ((a & 0x8)  << 1) |

         ((a & 0x10) >> 1) | ((a & 0x20) >> 3) |

         ((a & 0x40) >> 5) | ((a & 0x80) >> 7);

}

It gets every bit in the byte, and shifts it accordingly, starting from the first to the last.

Explanation:

   ((a & 0x1) << 7) //get first bit on the right and shift it into the first left position 

 | ((a & 0x2) << 5) //add it to the second bit and shift it into the second left position

  //and so on

For constant, 8-bit input, this costs no memory or CPU at run-time:

#define MSB2LSB(b) (((b)&1?128:0)|((b)&2?64:0)|((b)&4?32:0)|((b)&8?16:0)|((b)&16?8:0)|((b)&32?4:0)|((b)&64?2:0)|((b)&128?1:0))

I used this for ARINC-429 where the bit order (endianness) of the label is opposite the rest of the word. The label is often a constant, and conventionally in octal. For example:

#define LABEL_HF_COMM MSB2LSB(0205)

You may be interested in std::vector<bool> (that is bit-packed) and std::bitset

It should be the simplest as requested.

#include <iostream>

#include <bitset>

using namespace std;

int main() {

  bitset<8> bs = 5;

  bitset<8> rev;

  for(int ii=0; ii!= bs.size(); ++ii)

    rev[bs.size()-ii-1] = bs[ii];

  cerr << bs << " " << rev << endl;

}

Other options may be faster.

EDIT: I owe you a solution using std::vector<bool>

#include <algorithm>

#include <iterator>

#include <iostream>

#include <vector>

using namespace std;

int main() {

  vector<bool> b{0,0,0,0,0,1,0,1};

  reverse(b.begin(), b.end());

  copy(b.begin(), b.end(), ostream_iterator<int>(cerr));

  cerr << endl;

}

The second example requires c++0x extension (to initialize the array with {...}). The advantage of using a bitset or a std::vector<bool> (or a boost::dynamic_bitset) is that you are not limited to bytes or words but can reverse an arbitrary number of bits.

HTH

Table lookup or

uint8_t rev_byte(uint8_t x) {

    uint8_t y;

    uint8_t m = 1;

    while (m) {

       y >>= 1;

       if (m&x) {

          y |= 0x80;

       }

       m <<=1;

    }

    return y;

}

edit

Look here for other solutions that might work better for you

Before implementing any algorithmic solution, check the assembly language for whatever CPU architecture you are using. Your architecture may include instructions which handle bitwise manipulations like this (and what could be simpler than a single assembly instruction?).

If such an instruction is not available, then I would suggest going with the lookup table route. You can write a script/program to generate the table for you, and the lookup operations would be faster than any of the bit-reversing algorithms here (at the cost of having to store the lookup table somewhere).

a slower but simpler implementation:

static int swap_bit(unsigned char unit)

{

    /*

     * swap bit[7] and bit[0]

     */

    unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f));

    unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01))) | (unit & 0xfe));

    unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f));



    /*

     * swap bit[6] and bit[1]

     */

    unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf));

    unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02))) | (unit & 0xfd));

    unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf));



    /*

     * swap bit[5] and bit[2]

     */

    unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf));

    unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04))) | (unit & 0xfb));

    unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf));



    /*

     * swap bit[4] and bit[3]

     */

    unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef));

    unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08))) | (unit & 0xf7));

    unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef));



    return unit;

}

Can this be fast solution?

int byte_to_be_reversed = 

    ((byte_to_be_reversed>>7)&0x01)|((byte_to_be_reversed>>5)&0x02)|      

    ((byte_to_be_reversed>>3)&0x04)|((byte_to_be_reversed>>1)&0x08)| 

    ((byte_to_be_reversed<<7)&0x80)|((byte_to_be_reversed<<5)&0x40)|

    ((byte_to_be_reversed<<3)&0x20)|((byte_to_be_reversed<<1)&0x10);

Gets rid of the hustle of using a for loop! but experts please tell me if this is efficient and faster?

This simple function uses a mask to test each bit in the input byte and transfer it into a shifting output:

char Reverse_Bits(char input)

{    

    char output = 0;



    for (unsigned char mask = 1; mask > 0; mask <<= 1)

    {

        output <<= 1;



        if (input & mask)

            output |= 1;

    }



    return output;

}

This one is based on the one BobStein-VisiBone provided

#define reverse_1byte(b)    ( ((uint8_t)b & 0b00000001) ? 0b10000000 : 0 ) | 

                            ( ((uint8_t)b & 0b00000010) ? 0b01000000 : 0 ) | 

                            ( ((uint8_t)b & 0b00000100) ? 0b00100000 : 0 ) | 

                            ( ((uint8_t)b & 0b00001000) ? 0b00010000 : 0 ) | 

                            ( ((uint8_t)b & 0b00010000) ? 0b00001000 : 0 ) | 

                            ( ((uint8_t)b & 0b00100000) ? 0b00000100 : 0 ) | 

                            ( ((uint8_t)b & 0b01000000) ? 0b00000010 : 0 ) | 

                            ( ((uint8_t)b & 0b10000000) ? 0b00000001 : 0 ) 

I really like this one a lot because the compiler automatically handle the work for you, thus require no further resources.

this can also be extended to 16-Bits...

#define reverse_2byte(b)    ( ((uint16_t)b & 0b0000000000000001) ? 0b1000000000000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000000000010) ? 0b0100000000000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000000000100) ? 0b0010000000000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000000001000) ? 0b0001000000000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000000010000) ? 0b0000100000000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000000100000) ? 0b0000010000000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000001000000) ? 0b0000001000000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000010000000) ? 0b0000000100000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000000100000000) ? 0b0000000010000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000001000000000) ? 0b0000000001000000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000010000000000) ? 0b0000000000100000 : 0 ) | 

                            ( ((uint16_t)b & 0b0000100000000000) ? 0b0000000000010000 : 0 ) | 

                            ( ((uint16_t)b & 0b0001000000000000) ? 0b0000000000001000 : 0 ) | 

                            ( ((uint16_t)b & 0b0010000000000000) ? 0b0000000000000100 : 0 ) | 

                            ( ((uint16_t)b & 0b0100000000000000) ? 0b0000000000000010 : 0 ) | 

                            ( ((uint16_t)b & 0b1000000000000000) ? 0b0000000000000001 : 0 ) 

typedef struct

{

    uint8_t b0:1;

    uint8_t b1:1;

    uint8_t b2:1;

    uint8_t b3:1;

    uint8_t b4:1;

    uint8_t b5:1;

    uint8_t b6:1;

    uint8_t b7:1;

} bits_t;



uint8_t reverse_bits(uint8_t src)

{

    uint8_t dst = 0x0;

    bits_t *src_bits = (bits_t *)&src;

    bits_t *dst_bits = (bits_t *)&dst;



    dst_bits->b0 = src_bits->b7;

    dst_bits->b1 = src_bits->b6;

    dst_bits->b2 = src_bits->b5;

    dst_bits->b3 = src_bits->b4;

    dst_bits->b4 = src_bits->b3;

    dst_bits->b5 = src_bits->b2;

    dst_bits->b6 = src_bits->b1;

    dst_bits->b7 = src_bits->b0;



    return dst;

}

#include <stdio.h>

#include <stdlib.h>



int main()

{

    int i;

    unsigned char rev = 0x70 ; // 0b01110000

    unsigned char tmp = 0;



    for(i=0;i<8;i++)

    {

    tmp |= ( ((rev & (1<<i))?1:0) << (7-i));

    }

    rev = tmp;



    printf("%x", rev);       //0b00001110 binary value of given number

    return 0;

}

I think this is simple enough

uint8_t reverse(uint8_t a)

{

  unsigned w = ((a << 7) & 0x0880) | ((a << 5) & 0x0440) | ((a << 3) & 0x0220) | ((a << 1) & 0x0110);

  return static_cast<uint8_t>(w | (w>>8));

}

or

uint8_t reverse(uint8_t a)

{

  unsigned w = ((a & 0x11) << 7) | ((a & 0x22) << 5) | ((a & 0x44) << 3) | ((a & 0x88) << 1);

  return static_cast<uint8_t>(w | (w>>8));

}

unsigned char c ; // the original

unsigned char u = // the reversed

c>>7&0b00000001 |

c<<7&0b10000000 |

c>>5&0b00000010 |

c<<5&0b01000000 |

c>>3&0b00000100 |

c<<3&0b00100000 |

c>>1&0b00001000 |

c<<1&0b00010000 ;



Explanation: exchanged bits as per the arrows below.

01234567

<------>

#<---->#

##<-->##

###<>###

#define BITS_SIZE 8



int

reverseBits ( int a )

{

  int rev = 0;

  int i;



  /* scans each bit of the input number*/

  for ( i = 0; i < BITS_SIZE - 1; i++ )

  {

    /* checks if the bit is 1 */

    if ( a & ( 1 << i ) )

    {

      /* shifts the bit 1, starting from the MSB to LSB

       * to build the reverse number 

      */

      rev |= 1 << ( BITS_SIZE - 1 ) - i;

    }

  }



  return rev;

}

  xor ax,ax

  xor bx,bx

  mov cx,8

  mov al,original_byte!

cycle:   shr al,1

  jnc not_inc

  inc bl

not_inc: test cx,cx

  jz,end_cycle

  shl bl,1

  loop cycle

end_cycle:

reversed byte will be at bl register

How about this one...

int value = 0xFACE;



value = ((0xFF & value << 8) | (val >> 8);

This is an old question, but nobody seems to have shown the clear easy way (the closest was edW). I used C# (and the wonderful LinqPad to test this) but there's nothing in this example that couldn't be done easily in C.

Paste the following into the wonderful LinqPad (https://www.linqpad.net/), (which is where I tested this):

void PrintBinary(string prompt, int num, int pad = 8)

{

    Debug.WriteLine($"{prompt}: {Convert.ToString(num, 2).PadLeft(pad, '0')}");

}



int ReverseBits(int num)

{

    int result = 0;

    int saveBits = num;

    for (int i = 1; i <= 8; i++)

    {

        // Move the result one bit to the left

        result = result << 1;



        //PrintBinary("saveBits", saveBits);



        // Extract the right-most bit

        var nextBit = saveBits & 1;



        //PrintBinary("nextBit", nextBit, 1);



        // Add our extracted bit to the result

        result = result | nextBit;



        //PrintBinary("result", result);



        // We're done with that bit, rotate it off the right

        saveBits = saveBits >> 1;



        //Debug.WriteLine("");

    }



    return result;

}



void PrintTest(int nextNumber)

{

    var result = ReverseBits(nextNumber);



    Debug.WriteLine("---------------------------------------");

    PrintBinary("Original", nextNumber);

    PrintBinary("Reverse", result);

}



void Main()

{

    // Calculate the reverse for each number between 1 and 255

    for (int x = 250; x < 256; x++)

        PrintTest(x);

}