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?

Answer 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;
}

Answer 2

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;
}

Answer 3

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).

Answer 4

unsigned int rev_bits(unsigned int input)
{
    unsigned int output = 0;
    unsigned int n = sizeof(input) << 3;
    unsigned int i = 0;

    for (i = 0; i < n; i++)
        if ((input >> i) & 0x1)
            output |=  (0x1 << (n - 1 - i));

    return output;
}

Answer 5

You can reverse an unsigned 32-bit integer and return using the following reverse function :

unsigned int reverse(unsigned int A) {
    unsigned int B = 0;
    for(int i=0;i<32;i++){
        unsigned int j = pow(2,31-i);
        if((A & (1<<i)) == (1<<i)) B += j; 
    }
return B; 
}

Remember to include the math library. Happy coding :)

Answer 6

I believe the question is asking how to not output in reverse order.

Fun answer (recursion):

#include <stdio.h>

void print_bits_r(unsigned int x){
    if(x==0){
       printf("0");
       return;
    }
    unsigned int n=x>>1;
    if(n!=0){
       print_bits_r(n);
    }
    if(x&1){
        printf("1");
    }else{
        printf("0");
    }
}


void print_bits(unsigned int x){
    printf("%u=",x);
    print_bits_r(x);
    printf("\n");
}

int main(void) {
    print_bits(10u);//1010
    print_bits((1<<5)+(1<<4)+1);//110001
    print_bits(498598u);//1111001101110100110
    return 0;
}

Expected output:

10=1010
49=110001
498598=1111001101110100110

Sequential version (picks off the high-bits first):

#include <limits.h>//Defines CHAR_BIT
//....
void print_bits_r(unsigned int x){
    //unsigned int mask=(UINT_MAX>>1)+1u;//Also works...
    unsigned int mask=1u<<(CHAR_BIT*sizeof(unsigned int)-1u);
    int start=0;
    while(mask!=0){
        if((x&mask)!=0){
            printf("1");
            start=1;
        }else{
            if(start){
                printf("0");
            }
        }
        mask>>=1;
    }
    if(!start){
       printf("0");
    }    
}

Answer 7

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;
}

Answer 8

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).

Answer 9

It seems foolish to reverse the bit order of an integer value and then pick off bits from the low end, when it is trivial to leave it unchanged and pick off bits from the high end.

You want to convert an integer into a text representation, in this case in base-2 (binary). Computers convert integers into text all the time, most often in base-10 or base-16.

A simple built-in solution is:

printf('%b', 123);  // outputs 1111011

But that's not standard in C. (See Is there a printf converter to print in binary format?)

Numbers are written with the most-significant digit (or bit) first, so repeatedly taking the least-significant digit (or bit) is half the job. You have to collect the digits and assemble or output them in reverse order.

To display the value 123 as base-10, you would:

• Divide 123 by 10, yielding 12 remainder 3.
• Divide 12 by 10, yielding 1 remainder 2.
• Finally, divide 1 by 10, yielding 0 remainder 1. (0 is the stopping point.)
• Display the remainders (3, 2, 1) in reverse order, to display "123".

We could put any number of zeros before the 123, but that is not proper, because they do not contribute anything. Bigger numbers need longer character strings ("123", "123000", "123000000"). With this approach, you don't know how many digits are needed until you compute the most-significant digit, so you can't output the first digit until you have computed all of them.

Alternatively, you can compute the most-significant digit first. It looks a little more complex. Especially in bases other than base-2. Again starting with 123:

• Divide 123 by 1000, yielding 0 remainder 123.
• Divide 123 by 100, yielding 1 remainder 23.
• Divide 23 by 10, yielding 2 remainder 3.
• Finally, divide 3 by 1, yielding 3 remainder 0. (0 is the stopping point.)
• Display the quotients (0, 1, 2, 3) in the same order, skipping the leading zeros, to display "123".

You could output the digits in order as they are computed. You have to start with a large-enough divisor. For uint16 it's 10000; for uint32 it's 1000000000.

To display the value 123 as base-2, using the first method:

• Divide 123 by 2, yielding 61 remainder 1.
• Divide 61 by 2, yielding 30 remainder 1.
• Divide 30 by 2, yielding 15 remainder 0.
• Divide 15 by 2, yielding 7 remainder 1.
• Divide 7 by 2, yielding 3 remainder 1.
• Divide 3 by 2, yielding 1 remainder 1.
• Finally, divide 1 by 2, yielding 0 remainder 1. (0 is the stopping point.)
• Display the remainders (1,1,0,1,1,1,1) in reverse order, to display "1111011".

(Dividing by 2 can be accomplished by right-shifting by 1 bit.)

The second method yields the digits (bits) in order.

• Divide 123 by 256, yielding 0 remainder 123.
• Divide 123 by 128, yielding 0 remainder 123.
• Divide 123 by 64, yielding 1 remainder 59.
• Divide 59 by 32, yielding 1 remainder 27.
• Divide 27 by 16, yielding 1 remainder 11.
• Divide 11 by 8, yielding 1 remainder 3.
• Divide 3 by 4, yielding 0 remainder 3.
• Divide 2 by 2, yielding 1 remainder 1.
• Finally, divide 1 by 1, yielding 1 remainder 0. (0 is the stopping point.)
• Display the quotients (0,0,1,1,1,1,0,1,1) in the same order, skipping any leading first zeros, to display "1111011".

(These divisions can be accomplished using comparisons. The comparison values can be generated by dividing by 2, which means right-shifting by 1 bit.)

Any of these solutions might need a hack to prevent the value 0 from displaying as nothing (a.k.a. "", or the empty string) instead of "0".

Answer 10

You could reverse the bits like you output them, and instead store them in another integer, and do it again :

for (i = 0; i < (sizeof(unsigned int) * CHAR_BIT); i++)
{
  new_int |= (original_int & 1);
  original_int = original_int >> 1;
  new_int = new_int << 1;
}

Or you could just do the opposite, shift your mask :

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while (mask > 0)
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
}

If you want to remove leading 0's you can either wait for a 1 to get printed, or do a preliminary go-through :

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while ((mask > 0) && ((original_int & mask) == 0))
  mask = mask >> 1;
do
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
} while (mask > 0);

this way you will place the mask on the first 1 to be printed and forget about the leading 0's

But remember : printing the binary value of an integer can be done just with printf

Answer 11

I came up with a solution which dosesn't involve any application of bitwise operators. it is inefficient in terms of both space and time.

int arr[32];
for(int i=0;i<32;i++)
{
    arr[i]=A%2;
    A=A/2;
}
double res=1;
double re=0;
for(int i=0;i<32;i++)
{
    int j=31-i;
    res=arr[i];
    while(j>0)
    {
        res=res*2;
        j--;
    }
    re=re+res;
}
cout<<(unsigned int )re;

Answer 12

Here's a golang version of reverse bits in an integer, if anyone is looking for one. I wrote this with an approach similar to string reverse in c. Going over from bits 0 to 15 (31/2), swap bit i with bit (31-i). Please check the following code.

package main
import "fmt"

func main() {
    var num = 2
    //swap bits at index i and 31-i for i between 0-15
    for i := 0; i < 31/2; i++ {
        swap(&num, uint(i))
    }
    fmt.Printf("num is %d", num)
}

//check if bit at index is set
func isSet(num *int, index uint) int {
    return *num & (1 << index)
}

//set bit at index
func set(num *int, index uint) {
    *num = *num | (1 << index)
}

//reset bit at index
func reSet(num *int, index uint) {
    *num = *num & ^(1 << index)
}

//swap bits on index and 31-index
func swap(num *int, index uint) {
    //check index and 31-index bits
    a := isSet(num, index)
    b := isSet(num, uint(31)-index)
    if a != 0 {
        //bit at index is 1, set 31-index
        set(num, uint(31)-index)
    } else {
        //bit at index is 0, reset 31-index
        reSet(num, uint(31)-index)
    }
    if b != 0 {
        set(num, index)
    } else {
        reSet(num, index)
    }
}`

Answer 13

Here's my bit shift version which I think is very concise. Does not work with leading zeros though. The main idea is as follows

• Input is in variable a, final answer in b

• Keep extracting the right most bit from a using (a&1)

• OR that with b and left shift b to make place for the next bit

• Right shift a to go to the next bit

   #include <stdio.h>
  
   void main()
   {
     int a = 23;
     int b = 0;
     while(a!=0)
     {
       b = (b<<1)|(a&1);
       a = a>>1;
     }
     printf("reversed bits gives %d\n", b);
    }
  

Answer 14

The following make use of a table that stored all the reversed value of each byte, table[byte] == reversed_byte, and reverse the 4 bytes of the unsigned integer. Faster to compute than other answers.

#include <stdint.h>

uint32_t reverse_bits(uint32_t n) {
static const uint8_t table[256] =
    {
      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
    };

// 1 2 3 4 -> byte 4 becomes 1, 3 becomes 2, 2 becomes 3 and 1 becomes 4.
return (table[n & 0xff] << 24) | (table[(n >> 8) & 0xff] << 16) |
        (table[(n >> 16) & 0xff] << 8) | (table[(n >> 24) & 0xff]);
}