4
\$\begingroup\$

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;
}
\$\endgroup\$
13
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ You can generally count on the compiler to do the obvious optimizations like using shifts instead of multiply/divide. No need to rewrite arithmetic as bit shifts just to eke out a little extra performance if it is going to make your code any harder to read. In this case, however, since he really does want to do bit shifts, using the bit shift operators makes perfect sense and adds to the readability of the code. But if he were doing arithmetic and wanted to multiply a number by 2, he should use multiplication instead of trying to out optimize the compiler by using bit shifting. \$\endgroup\$ – Johnny Jan 6 '15 at 22:14
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ this fails when there are leading 0 bits in the input value \$\endgroup\$ – user3629249 Jan 6 '15 at 15:55
  • 2
    \$\begingroup\$ @user3629249 - works fine for me: ideone.com/J4jK61 \$\endgroup\$ – rolfl Jan 6 '15 at 15:58
  • \$\begingroup\$ I'd suggest two changes: 1) make all of the numbers unsigned rather than int and 2) use a for loop instead of a while loop as: for (result=0;value;value>>=1) \$\endgroup\$ – Edward Jan 6 '15 at 16:18
  • \$\begingroup\$ What happens when you input 6? \$\endgroup\$ – Edward Jan 6 '15 at 16:19
  • 3
    \$\begingroup\$ The answer to that, @Edward, heavily depends on what you expect as output to 1, similarly 2. I guess there are uncertainties in the question... it's not well specified. \$\endgroup\$ – rolfl Jan 6 '15 at 16:26
4
\$\begingroup\$

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 );
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You might want to consider what happens if input < 0. \$\endgroup\$ – Edward Jan 6 '15 at 15:45
  • 1
    \$\begingroup\$ @Edward except it's not allowed to be (see input contract) \$\endgroup\$ – ratchet freak Jan 6 '15 at 15:50
  • \$\begingroup\$ this will fail when there are leading 0 bits in the input number. suggest a for loop that iterates 32 times \$\endgroup\$ – user3629249 Jan 6 '15 at 15:53
  • 3
    \$\begingroup\$ @user3629249 check the contract, inputting 47 0b10111 should return 61 0b111101 \$\endgroup\$ – ratchet freak Jan 6 '15 at 15:55
  • 2
    \$\begingroup\$ @Edward I'm treating like it's the C spec, you give me something outside the spec you specified then anything can happen. \$\endgroup\$ – ratchet freak Jan 6 '15 at 16:22
2
\$\begingroup\$

Minor bugs

The problem states that N may be as large as 109. 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);
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ "systems with a 16-bit int are extremely rare these days". Do not agree about the rarity. Microchip made over a billion processors last year. A significant percentage of those have a native 8 or 16-bit integer size. Many C compilers use 16-bit int for them. \$\endgroup\$ – chux - Reinstate Monica Jan 10 '15 at 20:52
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I believe you have mis-read the spec. Not all bits need to be reversed, just the bits from the most significant set bit.... The spec says input 13 needs to become 11 .... and so on. \$\endgroup\$ – rolfl Jan 6 '15 at 16:20
  • 2
    \$\begingroup\$ Additionally, your definition of 32-bits to an int reminded me that int is only guaranteed as 16 bits in C. It's not necessarily 32-bit at all. \$\endgroup\$ – rolfl Jan 6 '15 at 16:27
  • \$\begingroup\$ OP's sample #1 has input 13 and output 11. This code gives output 2952790016. \$\endgroup\$ – chux - Reinstate Monica Jan 10 '15 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.