How to Print a Long Integer Using Only putchar()

How to Print a Long Integer Using Only putchar()

Here is a popular interview question: write a C/C++ function which outputs a long integer to the console:

void putlong(long number);

To make it harder, the interview often specifies the following restrictions:

  1. You can only use putchar(char c) as your only mean of outputing to the console
  2. Do not create a string buffer to store the digits (this is necessary to reverse the order of the digits)
  3. No stack to reverse the digits
  4. No recursion allowed

Before writing any code, let’s take a look at a simple example for number = 123. In the table below, we repeatedly extracting the last digit from the number using the modulus operator % and reduce the number by dividing it by 10.

Operation Result Note
123 % 10 3 This gives the third/last digit
123 / 10 12 The gives the remaining digits
12 % 10 2 This gives the second digit
12 / 10 1 This gives the remaining digits
1 % 10 1 This gives the first digit
1 / 10 0 This is when we stop

The problem with this approach is the extraction is in reverse order of what we should be printing out. There are several ways to address this issue. We can push the digits onto a stack and retrieve them in reverse order. However, restriction #3 prevents us from doing so. We can also use a char[] buffer to store the digits and later on output them in reverse order. As you guessed it, restriction #2 makes sure this will never happend. Restriction #4 also prevent us to use recursion as a way to print the digits in reverse order. So what’s left?

There are several solutions, but here is one that I devised: if we can reverse the digits in a number, then we can print them out in correct order. In the previous example where number == 123, if we can somehow reverse it so that number == 321 then we effectively solved the problem.

It turns out the reversing a number is not that hard, but we need to be aware of cases when overflow might occur. For example, on some machine, the range for long is -2147483648 to 2147483647. If we reverse the number near the limits, we get an overlow error. To remedy this problem, we can save off the last digit of the number, then reduce it by a factor of 10. This way, we can ensure that overflow will not happen. The code for saving the last digit and reducing the number looks like this:

char lastDigit = (char)((number % 10) + ‘0’); // Extract the last digit

number /= 10; // reduce the number

One last problem we need to address: the negative sign. At first, we might attempt to do something like:

if (number < 0)

{

putchar(‘-‘);

number *= -1;

}

However, it is not that simple. Recall that the range for long is -2147483648 to 2147483647. When number == -2147483648, changing sign the way we just did will produce an overflow. Thus, we will need to treat negative case with more care:

if (number < 0)
{

putchar(‘-‘);
lastDigit = (char)(‘0’ – (number % 10));
number /= -10;

}
else
{

lastDigit = (char)((number % 10) + ‘0’);
number /= 10;

}

Now that we save the last digit and reduce the number to prevent overflow, the fun begin. Our next task is to reverse the digits:

long reversed = 0;
while (number > 0)
{
reversed = reversed * 10 + (number % 10);
number /= 10;
}

Next, we will print out the digits of reverse:

while (reversed > 0)
{
char c = (char)((reversed % 10) + ‘0’);
putchar(c); // print it
reversed /= 10; // reduce the number
}

putchar(lastDigit); // don’t forget this

That’s all there to it. Below is the complete code in C, which also works in C++:


// putlong.c : Defines the entry point for the console application.// 
#include <stdio.h>
#include <limits.h>

void putlong(long number)
{
    char lastDigit;
    long reversed;

    // Extract the last digit and reduced the number by 10 to
    // avoid overflow. Also take care of the negative sign
    if (number < 0)
    {
        putchar('-');
        lastDigit = (char)('0' - (number % 10));
        number /= -10;
    }
    else
    {
        lastDigit = (char)((number % 10) + '0');
        number /= 10;
    }

    // Reverse the number
    reversed = 0;
    while (number > 0)
    {
        reversed = reversed * 10 + (number % 10);
        number /= 10;
    }

    // Now, output the number using only putchar()
    while (reversed > 0)
    {
        char c = (char)((reversed % 10) + '0');
        putchar(c);
        reversed /= 10;
    }
    putchar(lastDigit);
}

int main()
{
    putlong(0);
    putchar('\n');

    putlong(123456);
    putchar('\n');

    putlong(-123);
    putchar('\n');

    putlong(LONG_MAX);
    putchar('\n');

    putlong(LONG_MIN);
    putchar('\n');

    return 0;
}

If you have any comment or question, please post them at my blog.

Blogged with Flock

14 thoughts on “How to Print a Long Integer Using Only putchar()

  1. Christy

    I have a question regarding your code for printing out an integer using only putchar(). Or should I say rather an observation. When testing the code I realized that it actually does not process integers who have have repeating zeros. i.e. 10000. Just thought you might like to know.

  2. Christy

    I found a simple solution to this. add a veriable…

    int count = 0;

    in your first while loop add the line…

    count++;

    in the secound while loop add
    count–;

    then add a third while loop…
    while(count != 0)
    {
    putchar(‘0’);
    count–;
    }

    hope this was helpful.

  3. wuhrr Post author

    Christy, you are correct. My code is flawed and yours might fix it. I am now back to the drawing board and working on a) your solution, and b) possibly a different design (I am having an idea flying in my head, but it is bed time…)

    Thank you for pointing this out. I guess I need to do better testing.

  4. Pingback: Putlong() Revisited « Hai’s Tips and Thoughts

  5. Pingback: Putlong() Revisited « Hai’s Tips and Thoughts

  6. Pingback: PutLong Version 3 « Hai’s Blog

  7. evo

    Another solution … any holes on this one?

    void putlong(long n)
    {
    int pow = 1;
    char lastChar = ”;

    if (n < 0)
    {
    putchar(‘-‘);
    lastChar = (char)((int)’0′ + (n % 10));
    n = n / 10;
    n = n * (-1);
    }

    while (pow*10 <= n) pow = pow*10;

    while (pow != 0)
    {
    int d = n / pow;
    putchar((char)((int)’0’ + d));
    n = n – d * pow;
    pow = pow / 10;
    }

    if (lastChar != ”)
    {
    putchar(lastChar);
    }

    }

  8. wuhrr Post author

    To Evo: your code works perfectly, provide the following minor change:

    long d = n / pow // instead of int

  9. Arun

    in evo’s code:
    this line should be changed
    lastChar = (char)((int)’0′ + (n % 10));

    to:
    lastChar = (char)((int)’0′ + -(n % 10));

  10. NSF

    I don’t think evo’s actually works.
    Say we are gonna print 2147483647, pow would overflow in the first while loop.
    Neither does the author’s code since reversing that number would also result in overflow.

  11. Trey

    I understand this is old, hopefully someone responds…..i’m an amateur, working on a class assignment….why do you have to add the ‘0’? For instance.. if I have

    char number=(char)(1%10);
    printf(“%c”, number);

    The output is nothing…
    but for

    char number=(char)(1%10) + ‘0’;
    printf(“%c”, number);

    I get output of “1”…as expected from the modulus operator. Why is this? I don’t understand the function of the ‘0’ in this code
    Thanks

  12. Hai Post author

    The “(x%10)” expression will result in an int 0..9. ‘0’ is a char, whose ASCII value is 48. If you add (x%10) to ‘0’, you will get an int in range 48..57, which when casted to char, becomes ‘0’..’9′.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s