Custom uint16_t reverse function returns 0x8000

Question

    uint16_t ReverseInt16(uint16_t nonreversed) {
    uint16_t reversed = 0;
    reversed |= (nonreversed & 1 << 15) << 0; //check if bit 15 of nonreversed int is 1, if yes, write 1 to position 0, else write 0 to position 0
    reversed |= (nonreversed & 1 << 14) << 1;
    reversed |= (nonreversed & 1 << 13) << 2;
    reversed |= (nonreversed & 1 << 12) << 3;
    reversed |= (nonreversed & 1 << 11) << 4;
    reversed |= (nonreversed & 1 << 10) << 5;
    reversed |= (nonreversed & 1 << 9) << 6;
    reversed |= (nonreversed & 1 << 8) << 7;
    reversed |= (nonreversed & 1 << 7) << 8;
    reversed |= (nonreversed & 1 << 6) << 9;
    reversed |= (nonreversed & 1 << 5) << 10;
    reversed |= (nonreversed & 1 << 4) << 11;
    reversed |= (nonreversed & 1 << 3) << 12;
    reversed |= (nonreversed & 1 << 2) << 13;
    reversed |= (nonreversed & 1 << 1) << 14;
    reversed |= (nonreversed & 1 << 0) << 15;
    return reversed;
}

I need to bit-reverse uint16_t, so I wrote this function that reads bit by bit the original uint_t, and writes them to another uint, but in reverse bit position. The problem is, when I pass integer larger than 0x00 (0), the function returns maximum value of uint16_t.

I'm beginner in c bitwise operations.

Thank you for replies.

EDIT: The "Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C" uses 32bit ints!

Answer 1

I see two problems (operator precedence and wrong shifts), let us take an example, what you do for the first bit:

reversed |= (nonreversed & 1 << 15) << 0;

Operator precedence is misleading, & has a higher priority than <<, then it should be:

reversed |= (nonreversed & (1 << 15)) << 0;

Now let us see what it does, imagine nonreversed is 100000000000000b,

then (nonreversed & (1 << 15)) is 100000000000000b & 100000000000000b,

this gives 100000000000000b

If you shift it by 0, then it remains 100000000000000b (then 15th bit is not moved to position 0), thus if you want to invert the bit string, you need to say:

reversed |= (nonreversed & (1 << 15)) >> 15;

Same thing for the other bits (take care of operator precedence, and shift the bit at the right place). Legibility could be improved with a loop. Here is how I would implement it:

uint16_t ReverseInt16(uint16_t nonreversed) {
  uint16_t reversed = 0;
  for(uint16_t bit=0; bit<16; ++bit) {
     reversed |= (uint16_t)((nonreversed & (1 << bit) != 0)) << (15 - bit);
  }
  return reversed;
}

The expression nonreversed & (1 << bit) != 0 is a boolean, when converted to a uint16_t, it means 0 if false and 1 if true. 1 is a bit at position zero that I shift at the right place (<< (15 - bit)).

Answer 2

I think you mean the following :)

#include <stdio.h>
#include <stdint.h>

uint16_t ReverseInt16( uint16_t nonreversed ) 
{
    uint16_t reversed = 0;

    for ( uint16_t i = 0; i < 16; i++ )
    {
        reversed |= ( nonreversed >> ( 16 - i - 1 ) & 1 ) << i;
    }        

    return reversed;
}

int main( void )
{
    uint16_t x = 0x1234;

    printf( "%x\n", x );
    printf( "%x\n", ReverseInt16( x ) );

}    

The program output is

1234
2c48

As for your code then it does not reverse bits. For example, consider statement

reversed |= (nonreversed & 1 << 15) << 0;

1 << 15 gives in hexadecimal notation 8000

then for example if the MSB is set then (nonreversed & 1 << 15) gives also 8000. You need to shift the result right

reversed |= (nonreversed & 1 << 15) >> 15;

but you are trying to shift it left

reversed |= (nonreversed & 1 << 15) << 0;

Answer 3

To supplement some info about C Operator Precedence,

• Bitwise & has a lower priority than <<
  So, expression nonreversed & 1 << 15 is equivalent to nonreversed & (1 << 15). However, it is a good practise to use parentheses to make sure the precedence.

• Here is a typical usage which requires parentheses
  if ((a & mask) == flag) //the inner parentheses are required but easily forgotten

• C Operator Precedence table