Putlong() Revisited

In my previous post, I discussed and gave a solution to the putlong() problem. However, as Christy pointed out in her comment, my code did not work if a number has trailing zeros (e.g. 15700, 3000, 10, -10, …). Christy also suggested a fix, which I have not yet verified. As I tried to correct my code, I stepped back and thought, “what can I do differently?” and that is the topic of this post: a different way to solve the putlong() problem. In this post, I will discuss the problem, the strategy, caveats, and present the source itself.

The problem is a simple one: given a long integer, write it to the console (standard output) using only putchar(). The problem prohibits the candidate from using conversion or other output routines such as itoa, sprintf, … In addition, the problem prohibits the candidate from using array or any buffer. Finally, candidate should not use recursion.

Before I go on, it helps to review my other strategy in my previous post. This time around, my strategy is to extract each digit from left to right (i.e. most significant digit (MSD) to least significant digit (LSD)). As an example, let us examine the case where n=295 (n is the sole parameter to putlong). In this case, I will first extract and print the digit 2, then 9, and 5. To extract the first digit, 2, I divide n by 100, convert it to a character, and print it. Next, I remove the digit 2 from n using the modulus operator: 295 % 100 = 95. In similar fashion, I extract the next digit, 9, by dividing n by 10: 95 / 10 = 9. The logic then goes on until I extracted all the digits. Reader should notice that the same number 100 used to extract the MSD is also used to remove that MSD from n.

The question is, how do I come up with 100? For my solution, I will introduce a local variable called extractor (line 11), which is a long integer whose value is either a 1 or a multiple of 10 (1, 10, 100, 1000, and so on). The key is to build extractor so that it contains the same number of digits as n. To achieve this goal, I started out with extractor = 1, then keep multiply it by 10 until n / extractor produces a single-digit number (lines 14-15). After building the extractor, I will go through the cycles of extracting the MSD, convert to character type, write it out, and remove the MSD from the number. These cycle will end when I am running out of digits (lines 25-31).

At this point, I am not done yet becase I have to address two caveats: negative numbers and trailing zeros. So far, my discussion did not include negative numbers. For a background on how troublesome negative numbers are, please refer to my previous post. To deal with negative numbers, I modified my code to build the extractor as a negative multiple of 10: -1, -10, -100, and so on (lines 14-15). Next, I write the negative sign (line 18-19) and it should take care of the case.

At this point, the code passes most of my test cases, except for the cases that prompted me to rewrite putlong() in the first place: numbers with trailing zeros (e.g. 15700, 3000, 10, -10, and so on). Take the case where n=50; after extracting the digit 5 and print it (lines 27-28), removing the 5 will leave n=0 (line 29), and extractor=1 (line 30). With n=0, I exit the loop (lines 25-31) and did not write the last zero. Similarly, for the case of 3000, I only write out the digit 3 and exit the loop with extractor=100. Observe the value of extractor after exiting the loop (lines 25-31): when n=50, extractor=1 and when n=3000, extractor=100. That means the number of digits in extractor corresponds to the number trailing zeros I need to write and that is how I take care of trailing zeros (lines 37-38).

Here is the complete listing of my code for putlong() version 2. As usual, I would like to hear from the reader of any suggestion, comments, or bug report.

<div><pre>    1         /// <summary>
   2         /// Writes a long number to the console.
   3         /// Constraints:
   4         /// 1. Use only putchar() and no other means (itoa, sprintf, ...)
   5         /// 2. Do not use array to store the digits
   6         /// 3. No recursion
   7         /// </summary>
   8         /// <param name="n">The number to write to the console</param>
   9         public static void putlong(long n)
  10         {
  11             long extractor; // .., -100, -10, 1, 10, 100, .. to extract the digits
  13             // Build the extractor so that (n / extractor) is a single digit [0-9]
  14             for (extractor = (n < 0 ? -1 : 1); n / extractor >= 10; extractor *= 10)
  15                 ;
  17             // Case: n is negative.
  18             if (n < 0)
  19                 putchar('-');
  21             // Now, we extract the digits starting with the most significant digit
  22             // (left-most) and work our way to the least significant digit (right-
  23             // most). The number now is always positive because of the previous
  24             // block.
  25             while (n != 0)
  26             {
  27                 char digit = (char)(n / extractor + '0');
  28                 putchar(digit);
  29                 n %= extractor;
  30                 extractor /= 10;
  31             }
  33             // take care of trailing zeros: As long as the extractor is not zero,
  34             // we are not done. A non-zero extractor means we have trailing zeros.
  35             // For example, a 1000 means we need to write out 4 (yes, 4; not 3)
  36             // trailing zeros.
  37             for (; extractor != 0; extractor /= 10)
  38                 putchar('0');
  39         }

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s