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
Hai's DevBits 