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:
- You can only use putchar(char c) as your only mean of outputing to the console
- Do not create a string buffer to store the digits (this is necessary to reverse the order of the digits)
- No stack to reverse the digits
- 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
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.
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.
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.
Pingback: Putlong() Revisited « Hai’s Tips and Thoughts
Pingback: Putlong() Revisited « Hai’s Tips and Thoughts
Pingback: PutLong Version 3 « Hai’s Blog
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);
}
}
To Evo: your code works perfectly, provide the following minor change:
long d = n / pow // instead of int
in evo’s code:
this line should be changed
lastChar = (char)((int)’0′ + (n % 10));
to:
lastChar = (char)((int)’0′ + -(n % 10));
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.
The easiest way should be using a stack.
@NSF: This is a typical interview question, that means you are not allowed to use stack.
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
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′.