Reversed Binary Numbers

Question

Here is my code for "Reverse Binary Numbers" in C.

Problem

Your task will be to write a program for reversing numbers in binary. For instance, the binary representation of 13 is 1101, and reversing it gives 1011, which corresponds to number 11.

Input

The input contains a single line with an integer \$N\$, (where \$1≤N≤1000000000\$ ).

Output Output one line with one integer, the number we get by reversing the binary representation of \$N\$.

Sample 1

• input 13
• output 11

Sample 2

• input 47
• output 61

It's pretty efficient, but not the best. I wanted to improve the runtime. So I am looking for suggestions to improve the code.

Code

//Reverse Binary

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define DIVISOR 2
#define MAX 50

int main() {
  int r, q, n, m = 1, num = 0, i = 0, len;
  int res[MAX];
  char str[MAX];

  scanf("%d", &n);

  do {

    q = n / DIVISOR;
    r = n % DIVISOR;

    res[i] = r; 

    n = q;

    i++;

  } while(n > 0);

  len = i;
  m = 1;

  for(; i > 0; i--) {
    if(res[i - 1] != 0) {
      num += res[i - 1] * m;
    }
    m *= DIVISOR;
  }

  fprintf(stdout, "%d", num);

  return 0;
}

Answer 1

Division and multiplication are relatively computationally costly operations compared to shifts and AND operations. Try to reformulate your answer in terms of >> and & and you will likely find a performance gain.

Other things I noticed that may help you improve your program:

Eliminate unused variables

Both len and str are unused and may be eliminated from the program.

Try to put the loop exit condition at the top of the loop

Instead of using do {...} while, prefer to use while {...} or a for loop. in your case this will also neatly solve the problem that occurs when the user types in a negative number.

return 0 is not needed at the end of main

Any modern compiler will automatically assume that getting to the end of main means that the program has executed successfully and will generate the equivalent of return 0 at the end. It is not necessary to write it.

Check the return value of scanf

The call to scanf can fail, in which case it will return 0. Your code should check for that.

If your input says you will only have positive numbers, use unsigned

Instead of "%d" it would make more sense to say scanf("%u", &n) since the inputs cannot be negative. Note that this will not prevent negative numbers from being input, but it makes the expectation clear within the code. Alternatively, check for negative number input to make the code more robust.

Consider verifying that your data type will hold the maximum value

The input specification says that the input numbers are all in the range of \$1 \le N \le 1,000,000,000\$ but an int isn't necessarily large enough on all platforms. Since it takes 30 bits to express that number, and because it's unsigned, it would probably make more sense to use a uint_fast32_t type defined in <stdint.h> which is a fast integer type containing at least 32 bits.

Answer 2

Putting all your code in the main method is seldom a good idea.

Additionally, int is only guaranteed to 16 bits, you need to use long.

This problem lends itself to creating a function to do the work for you:

unsigned long bitReverse(unsigned long value)
{
    unsigned long result = 0;
    while (value)
    {
        /* make space by shifting left on the result */
        result <<= 1;
        /* add the low bit in to the space */
        result |= value & 1;
        /* get a new low bit. */
        value >>= 1;
    }
    return result;
}

The above function takes the low-bit off of the input value, and feeds them to the high bits of the output value.

I have put this together in a simple ideone

Answer 3

Using bit trick you can reverse the bits in a number without needing arrays to store temporary results.

modifying one solution I found online:

unsigned int input;
scanf("%u", &input);
unsigned int result = 0;

while(input !=0)
{   
  result  <<= 1;
  result  |= input & 1;
  input >>=1;
}
fprintf(stdout, "%d", result );

Answer 4

Minor bugs

The problem states that N may be as large as 10⁹. An int is only guaranteed to hold values up to 32767. Granted, systems with a 16-bit int are extremely rare these days, but you should use a long for correctness. Since we are working with digits, unsigned long would be more appropriate.

It is conventional to output a newline at the end of your output.

Trimming the fat

You have a lot of variables, which makes it hard to follow what is going on.

You should always compile with warnings enabled. Your compiler would have told you…

13:8: warning: unused variable 'str' [-Wunused-variable]
  char str[MAX];
       ^
1 warning generated.

You have other unnecessary (len, q, r) and cryptically named (m, res) variables, as well as superfluous includes (<stdlib.h> and <string.h>). DIVISOR is also being used as a multiplier, so I would rename it to BASE. The length of the array (50) seems completely arbitrary; there is a systematic way to figure out exactly how much storage you need.

//Reverse Binary

#include <stdio.h>

#define BASE 2
#define NUM_DIGITS (8 * sizeof(unsigned long))

int main() {
  unsigned long n;
  int i = 0;
  int digits[NUM_DIGITS];       // Least-significant digit first

  scanf("%lu", &n);

  do {
    digits[i++] = n % BASE;
  } while ((n = n / BASE) != 0);

  unsigned long num = 0, multiplier = 1;

  for (i--; i >= 0; i--) {
    num += digits[i] * multiplier;
    multiplier *= BASE;
  }

  fprintf(stdout, "%lu\n", num);
}

Rewriting

The key to the solution lies in picking an invariant: on each iteration of the loop, transfer one digit from the input to the output.

I would write it using a for loop, so that you can see at a glance what happens to the input just by looking at the loop header.

#include <stdio.h>
#define BASE 2

int main() {
    unsigned long in, out = 0;
    for (scanf("%lu", &in); in; in /= BASE) {
        out = (out * BASE) + (in % BASE);
    }
    printf("%lu\n", out);
}

Since the problem deals with binary digits, it seems natural to write the same algorithm using bitwise operations. (When compiling with optimizations enabled, the generated executable is likely to be identical.)

#include <stdio.h>

int main() {
    unsigned long in, out = 0;
    for (scanf("%lu", &in); in; in >>= 1) {
        out = (out << 1) | (in & 1);
    }
    printf("%lu\n", out);
}

Answer 5

Remember that ALL the bits need to be reversed, not just the '1' bits. The following code compiles, links cleanly and works properly.

#include <stdio.h>
#include <stdlib.h>

#define INT_BITS (32)

int main()
{
    unsigned int input;
    unsigned int result = 0;
    unsigned int i; // loop counter

    printf("\nEnter the unsigned Number: ");
    if( 1 != scanf("%u", &input) )
    { // scanf failed
        perror( "scanf failed" );
        exit( EXIT_FAILURE );
    }

    // implied else, scanf successful

    for(i=0;i<INT_BITS;i++)
    {
      result  <<= 1;
      result  |= input & 1;
      input >>=1;
    } // end for

    fprintf(stdout, "%u\n", result );

    return(0);
} // end function: main