C reverse bits in unsigned integer

Question

I'm converting an unsigned integer to binary using bitwise operators, and currently do integer & 1 to check if bit is 1 or 0 and output, then right shift by 1 to divide by 2. However the bits are returned in the wrong order (reverse), so I thought to reverse the bits order in the integer before beginning.

Is there a simple way to do this?

Example: So if I'm given the unsigned int 10 = 1010

while (x not eq 0) 
  if (x & 1)
    output a '1'
  else 
    output a '0'
  right shift x by 1

this returns 0101 which is incorrect... so I was thinking to reverse the order of the bits originally before running the loop, but I'm unsure how to do this?

Solution 1

Reversing the bits in a word is annoying and it's easier just to output them in reverse order. E.g.,

void write_u32(uint32_t x)
{
    int i;
    for (i = 0; i < 32; ++i)
        putchar((x & ((uint32_t) 1 << (31 - i)) ? '1' : '0');
}

Here's the typical solution to reversing the bit order:

uint32_t reverse(uint32_t x)
{
    x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1);
    x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2);
    x = ((x >> 4) & 0x0f0f0f0fu) | ((x & 0x0f0f0f0fu) << 4);
    x = ((x >> 8) & 0x00ff00ffu) | ((x & 0x00ff00ffu) << 8);
    x = ((x >> 16) & 0xffffu) | ((x & 0xffffu) << 16);
    return x;
}

Solution 2

You could just loop through the bits from big end to little end.

#define N_BITS (sizeof(unsigned) * CHAR_BIT)
#define HI_BIT (1 << (N_BITS - 1))

for (int i = 0; i < N_BITS; i++) {
     printf("%d", !!(x & HI_BIT));
     x <<= 1;
}

Where !! can also be written !=0 or >> (N_BITS - 1).

Solution 3

you could move from left to right instead, that is shift a one from the MSB to the LSB, for example:

unsigned n = 20543;
unsigned x = 1<<31;
while (x) {
    printf("%u ", (x&n)!=0);
    x = x>>1;
}

Solution 4

The Best way to reverse the bit in an integer is:

1. It is very efficient.
2. It only runs upto when the leftmost bit is 1.

CODE SNIPPET

int reverse ( unsigned int n )
{
    int x = 0;
    int mask = 1;
    while ( n > 0 )
    {
        x = x << 1;
        if ( mask & n )
            x = x | 1;
        n = n >> 1;
    }
    return x;
}

Solution 5

The 2nd answer by Dietrich Epp is likely what's best on a modern processor with high speed caches. On typical microcontrollers however that is not the case and there the following is not only faster but also more versatile and more compact (in C):

// reverse a byte
uint8_t reverse_u8(uint8_t x)
{
   const unsigned char * rev = "\x0\x8\x4\xC\x2\xA\x6\xE\x1\x9\x5\xD\x3\xB\x7\xF";
   return rev[(x & 0xF0) >> 4] | (rev[x & 0x0F] << 4);
}

// reverse a word
uint16_t reverse_u16(uint16_t x)
{
   return reverse_u8(x >> 8) | (reverse_u8(x & 0xFF) << 8);
}

// reverse a long
uint32_t reverse_u32(uint32_t x)
{
   return reverse_u16(x >> 16) | (reverse_u16(x & 0xFFFF) << 16);
}

The code is easily translated to Java, Go, Rust etc. Of course if you only need to print the digits, it is best to simply print in reverse order (see the answer by Dietrich Epp).

View more solutions

Comments

[asaelr]

Just remember to multiply the sizeof by 8, and your First solution will be fine. (The second will overflow, but with some corrections, it can work)

[Paul R]

Better still, multiply by CHAR_BIT.

[iabdalkader]

@SethCarnegie no, it's x>>1 because x=1<<31 so we're moving from the MSB to LSB or left to right to reverse the order of the bits.

[Seth Carnegie]

Ah I had confused x with n.

[Admin]

How would I discard leading 0s from the output in this case? I could check and not output until it has detected a true bit, but that doesn't seem very elegant and also wouldn't work if the input to the program is 0.

[iabdalkader]

Isn't !!(x) == x ? double negation cancels out, and ==0 will be true, i.e 1 if it's 0 so it prints the bits flipped.

[Eregrith]

@user1139103 I added leading 0 removal in my answer, changing to a do/while to keep the last 0. You can also use while ((mask > 1) ... in the first while and keep the second as while (mask > 0)

[Eregrith]

@asaelr what could overflow ? there is no multiplication or shift to the left in the second solution

[iabdalkader]

isn't original_int & mask is either 0 or a number >= 1 depending on the bit position, and not 0/1 ?

[asaelr]

No shifting to the left? what about 1 << (sizeof(unsigned int) * CHAR_BIT)?

[Fred Foo]

@mux: no, double negation only cancels out for 0 and 1. You're right about ==0, that should have been !=0, sorry.

[iabdalkader]

oh I see it now, something like !(!(512)) = !(0) = 1 thanks, I blame it on too much discrete :) ...

[Admin]

@Eregrith I'm unsure why but it doesn't output anything for odd numbers

[Eregrith]

@asaelr okay I think the error was 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1) right ? @user1139103 try it out with this version.

[Tomas Pruzina]

Could u please give me further explanation of second part (or give me a phrase to put into google). It does not make sense to me and my knowledge about bit representation is appearantly worse than I thought. Thank you in advance.

[Dietrich Epp]

@AoeAoe: It's a bit twiddling hack. I suggest writing out the numbers in binary if you want to understand how it works. Each line exchanges the positions of half of the bits with another half, and the five lines in the core can be written in any order.

[Shital Shah]

Here's explanation: Let us divide all bits in block size b, starting with b=1. Now we swap each adjacent block. Double block size and repeat. Continue until block size is half of word size. For 32 bits, this will be 5 steps. Each step can be written as ((x & mask) << b) | ((x & mask') << b). Thus in 5 statements, we can reverse 32 bit int.

[chqrlie]

0x1 << 31 has undefined behavior. You should write output |= 1U << (n - 1 - i);

[chqrlie]

To avoid undefined behavior on 1 << 31, you should use if((A & (1U<<i)) == (1U<<i)) B += j; Also use unsigned int j = 1U << (31 - i); instead of floating point arithmetics.

[chqrlie]

Faster to compute than other answers: Did you benchmark your proposal against the other answers? How much faster is it?

[Antonin GAVREL]

yes I did. So basically it is way faster than all branching solutions (while, for etc) and very slightly faster than divide and conquer. I missed user103185's answer, will test later and provide the benchmark.