分类： C/C++
2013-03-23 10:04:38
Part of
by
Copyright © 1999, Douglas. W. Jones, with major revisions mad e in 2002 and a small update in 2007. This work may be transmitted or stored in electronic form on any computer attached to the Internet or World Wide Web so long as this notice is included in the copy. Individuals may make single copies for their own use. All other rights are reserved.
| Rated as a top 50 site by as of Feb 2002. |
Programmers on binary computers have always faced computational problems when dealing with textual input-output because of our convention that printed numeric data should be represented in base 10. These problems have never been insurmountable, but they are particularly annoying when writing programs for machines with limited capacity in their arithmetic units. Suppose, for example, you have an unsigned binary number that you wish to print out in decimal form. The following C code will do this:
void putdec( unsigned int n )
{
unsigned int rem = n % 10;
unsigned int quot = n / 10;
if (quot > 0) putdec( quot );
putchar( rem + '0' );
}
The problem with this C code is that it assumes that the computer's arithmetic unit is sufficiently large to handle the entire number n, and it assumes that the arithmetic unit can conveniently do integer division yielding both a quotient and a remainder. These assumptions are not always reasonable, both because many commercially successful computers do not include division hardware and because, even when such hardware is available, it is of little direct use when dividing numbers larger than the ALU can handle.
The focus of this tutorial is on writing fast code to convert unsigned 16 bit binary numbers to decimal on a machine with an 8-bit ALU and no divide instruction. This situation is common on small microcontrollers, and the techniques generalize in useful ways, for example, to the problem of doing 64 bit binary to decimal conversion using a 32 bit ALU.
On machines with no divide instruction where speed is no issue, it may be better to simply use repeated subtraction instead of the fast but algebraically complex code given in the body of this tutorial. Consider the following 16-bit conversion code as an example:
void putdec( int n )
{
char a, b, c, d;
if (n < 0) {
putchar( '-' );
n = -n;
}
for ( a = '0' - 1; n >= 0; n -= 10000 ) ++a;
for ( b = '9' + 1; n < 0; n += 1000 ) --b;
for ( c = '0' - 1; n >= 0; n -= 100 ) ++c;
for ( d = '9' + 1; n < 0; n += 10 ) --d;
putchar( a );
putchar( b );
putchar( c );
putchar( d );
putchar( n + '0' );
}
Variants on the clever algorithm given above have been very popular on 8-bit microprocessors and microcontrollers, despite the fact that conversions can require over 30 iterations of the for loops in this code.
To do the conversion faster, what we'll do is look at our binary number as a base 16 number and then do the conversion in terms of the base 16 digits. Consider a 16 bit number n . This can be broken into 4 fields of 4 bits each, the base 16 digits; call them n 3 , n 2 , n 1 and n 0 .
n
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
| n | n | n | n |
3 2 1 0
The value of the number can be expressed in terms of these 4 fields as follows:
n = 4096n 3 + 256n 2 + 16n 1 + n 0
In the same way, if the value of n , expressed in decimal, is d 4 d 3 d 2 d 1 d 0 , where each of d 4 , d 3 , d 2 , d 1 and d 0 are decimal digits, the value of n can be expressed as:
n = 10000d 4 + 1000d 3 + 100d 2 + 10d 1 + d 0
Our problem then, is to compute the d i from the n i without dealing directly with the larger number n .
To do this, we first note that the factors used in combining the values of n i can themselves be expressed as sums of multiples of powers of 10. Therefore, we can rewrite the original expression as:
n =
n 3 ( 4×1000 + 0×100 + 9×10 + 6×1 ) +
n 2 ( 2×100 + 5×10 + 6×1 ) +
n 1 ( 1×10 + 6×1 ) +
n 0 ( 1×1 )
If distribute the n i over the expressions for each factor, then factor out the multiples of 100, we get the following:
n =
1000(4n 3 ) +
100(0n 3 + 2n 2 ) +
10(9n 3 + 5n 2 + 1n 1 ) +
1(6n 3 + 6n 2 + 6n 1 + 1n 0 )
We can use this to arrive at first approximations a i for d 3 through d 0 :
a 3 = 4n 3
a 2 = 0n 3 + 2n 2
a 1 = 9n 3 + 5n 2 + 1n 1
a 0 = 6n 3 + 6n 2 + 6n 1 + 1n 0
The values of a i are not proper decimal digits because they are not properly bounded in the range 0 < a i < 9. Instead, given that each of n i is bounded in the range 0 < n i < 15, the a i are bounded as follows:
0 < a 3 < 60
0 < a 2 < 30
0 < a 1 < 225
0 < a 0 < 285
This is actually quite promising because a 3 through a 1 are less than 256 and may therefore be computed using an 8 bit ALU, and even a 0 may be computed in 8 bits if we can use the carry-out bit of the ALU to hold the high bit. Furthermore, if our interest is 2's complement arithmetic where the high bit is the sign bit, the first step in the output process is to print a minus sign and then negate, so the constraint on n 3 becomes 0 < n 3 < 8 and we can conclude naively that
0 < a 0 < 243
Note that we said n 3 < 8 and not n 3 < 8; this is because of the one negative number in the 2's complement system that cannot be properly negated, -32768. If we exclude this number from the range of legal values, the upper bound is reduced to 237; in fact, this is the overall upper bound, because in the one case where n 3 is 8, all of the other n i are zero, so we can assert globally that
0 < a 0 < 237
Even with our naive bound, however, it is easy to see that we can safely use 8 bit arithmetic to accumulate all of the a i .
Given that we have computed the a i , we can push them into the correct ranges by a series of 8-bit divisions and one 9-bit division, as follows:
c 1 = a 0 / 10
d 0 = a 0 mod 10
c 2 = (a 1 + c 1 ) / 10
d 1 = (a 1 + c 1 ) mod 10
c 3 = (a 2 + c 2 ) / 10
d 2 = (a 2 + c 2 ) mod 10
c 4 = (a 3 + c 3 ) / 10
d 3 = (a 3 + c 3 ) mod 10
d 4 = c 4
In the above, the c i terms represent carries propagated from one digit position to the next. The upper bounds on each of the c i can be computed from the bounds given above for the a i :
c 1 < 28 [ = 285/10 ]
c 2 < 25 [ = (28 + 225)/10 = 253/10 ]
c 3 < 5 [ = (25 + 30)/10 = 55/10 ]
c 4 < 6 [ = (5 + 60)/10 = 65/10 ]
In computing the bound on c 2 , we came within 2 of to 255, the maximum that can be represented in 8 bits, so an 8 bit ALU is just barely sufficient for this computation. Again, if we negate any negative numbers prior to output, so that the maximum value of n 3 is 8, the bound on c 1 becomes 23 instead of 28.
A first hack at reducing the above idea to code might include named temporaries for all of the terms used above, but we can avoid this if we reorganize things slightly and note that, after computing each digit of the number, we no-longer need one of the n i . This leads to the following C code, assuming that C allocates 16 bits to items of type short int and 8 bits to items of type char :
void putdec( unsigned short int n )
{
unsigned char d4, d3, d2, d1, q;
unsigned short int d0;
d0 = n & 0xF;
d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12) & 0xF;
d0 = 6*(d3 + d2 + d1) + d0;
q = d0 / 10;
d0 = d0 % 10;
d1 = q + 9*d3 + 5*d2 + d1;
q = d1 / 10;
d1 = d1 % 10;
d2 = q + 2*d2;
q = d2 / 10;
d2 = d2 % 10;
d3 = q + 4*d3;
q = d3 / 10;
d3 = d3 % 10;
d4 = q;
putchar( d4 + '0' );
putchar( d3 + '0' );
putchar( d2 + '0' );
putchar( d1 + '0' );
putchar( d0 + '0' );
}
Of course, the above code prints all 5 digits of n instead of only printing the significant digits, but this can be fixed in many ways. The following fix is perhaps the cleanest, making effective use of partial results as soon as those results can be used to predict that digits will be zero. Even so, adding these features to the code obscures the computation being performed.
void putdec( unsigned short int n )
{
unsigned char d4, d3, d2, d1, q;
unsigned short int d0;
d0 = n & 0xF;
d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12);
d0 = 6*(d3 + d2 + d1) + d0;
q = d0 / 10;
d0 = d0 % 10;
d1 = q + 9*d3 + 5*d2 + d1;
if (d1 != 0) {
q = d1 / 10;
d1 = d1 % 10;
d2 = q + 2*d2;
if ((d2 != 0) || (d3 != 0)) {
q = d2 / 10;
d2 = d2 % 10;
d3 = q + 4*d3;
if (d3 != 0) {
q = d3 / 10;
d3 = d3 % 10;
d4 = q;
if (d4 != 0) {
putchar( d4 + '0' );
}
putchar( d3 + '0' );
}
putchar( d2 + '0' );
}
putchar( d1 + '0' );
}
putchar( d0 + '0' );
}
To print signed values, we can replace the first few lines of the above code with the following:
void putdec( int n )
{
unsigned char d4, d3, d2, d1, d0, q;
if (n < 0) {
putchar( '-' );
n = -n;
}
d0 = n & 0xF;
d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12) & 0xF;
/* the remainder of the code is unchanged */
As mentioned earlier, forcing n positive prior to breaking it down into nibbles allows us to use a char type for d0 instead of a short int type.
Note that the computation of d3 has also changed as a result of the change from unsigned to signed arithmetic. This is because the right-shift operator shifts zeros into the high bit when applied to unsigned numbers, but it replicates the sign bit when applied to signed numbers. There is one case in 16 bit 2's complement arithmetic where both n and -n are negative, that is, n = -32768. The change we have made gives us the correct output in this case.
In the code given above for unsigned printing, the fact that a 0 could be as large as 285 forced us to declare the variable d0 as short int instead of char . We can avoid this by observing that the final addition in the sum used to compute a 0 is the only one that will push this sum over 255, and therefore, we need only check the carry bit once to detect overflow. Having detected overflow, we can account for it in the computation that follows:
void putdec( unsigned short int n )
{
unsigned char d4, d3, d2, d1, d0, q;
d0 = n & 0xF;
d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12) & 0xF;
if ( (6*(d3 + d2 + d1) + d0) > 255 ) { /* overflow */
d0 = (6*(d3 + d2 + d1) + d0) & 0xFF;
q = d0/10 + 25;
d0 = d0 % 10 + 6;
if (d0 >= 10) {
d0 = d0 - 10;
q = q + 1;
}
} else { /* no overflow */
d0 = 6*(d3 + d2 + d1) + d0;
q = d0 / 10;
d0 = d0 % 10;
}
In the above code, after having noted an overflow in the computation of a 0 , we retain the least significant bits of the sum in d0 and then approximately correct the quotient by adding 256/10, or 25; correcting this and computing the correct remainder is a bit more interesting.
Given some integer i > 256, if we want to compute i mod 10 from (i - 256) mod 10, we need to note that the modulus operator is distributive in an interesting sense:
(i + j ) mod m = ((i mod m ) + (j mod m )) mod m
Using this, we can conclude that:
i mod 10 = (((i - 256) mod 10) + (256 mod 10)) mod 10
= (((i - 256) mod 10) + 6) mod 10
In the case where ((i - 256) mod 10) + 6 is greater than 10, the truncation of the quotient was also incorrect, so we must add 1 to the approximate quotient as well. This justifies the code given above, and this code has also been tested exhaustively for all integers from 0 to 65535.
If flat-out speed is not of the essence, the easiest way to do the required divisions is to use the trivial repeated subtraction algorithm. The largest dividend we must consider is only 285, so it will take no more than 28 iterations for this division.
/* quotient and remainder returned by div10 */
unsigned char q, r;
void div10( unsigned char i )
{
q = 0;
r = i;
while (r > 9) {
q = q + 1;
r = r - 10;
}
}
This can be optimized in several ways. Most notably, termination conditions that compare with zero are almost always significantly faster than those that compare with other constants, so we might write something like this:
/* quotient and remainder returned by div10 */
unsigned char q, r;
void div10( unsigned char i )
{
q = -1;
r = i;
do {
q = q + 1;
r = r - 10;
} while (r >= 0);
r = r + 10;
}
covers the problem of doing multiplicaton and division using only shift and add instructions. We use the results presented there, taking specific advantage of the limited ranges of values occupied by our dividends, to completely eliminate iteration from our code.
There are two ways to get an exact quotient and remainder from i /10 using reciprocal multiplication in 8 bits. Either we multiply by 0.00011001 to get an approximate quotient and then compute the remainder and correct the quotient, or we multiply by 0.00011001101 to get an exact quotient from which we can compute the remainder.
The former method, yielding an approximation, can be reduced to the following C code:
/* quotient and remainder returned by div10 */
unsigned char q, r;
void div10( unsigned char i )
{
/* approximate the quotient as q = i*0.000110011 (binary) */
q = ((i>>1) + i) >> 1; /* times 0.11 */
q = ((q>>4) + q) >> 3; /* times 0.000110011 */
/* compute the reimainder as r = i - 10*q */
r = ((q<<2) + q) << 1; /* times 1010. */
r = i - r;
/* fixup if approximate remainder out of bounds */
if (r >= 10) {
r = r - 10;
q = q + 1;
}
}
In first two right-shift-and-add statements used above, we have assumed that the carry out of the high bit of the add operation is shifted into the high bit of the second of the two right-shift operations used in each statement. This can be done efficiently in many machine instruction sets, but even good optimizing compilers may insist on using a 16 bit accumulator for all intermediate results of arithmetic operations.
The second approach, using a more elaborate multiplier to give an exact quotient, may be coded as follows:
/* quotient and remainder returned by div10 */
unsigned char q, r;
void div10( unsigned char i )
{
/* approximate the quotient as q = i*0.00011001101 (binary) */
q = ((i>>2) + i) >> 1; /* times 0.101 */
q = ((q ) + i) >> 1; /* times 0.1101 */
q = ((q>>2) + i) >> 1; /* times 0.1001101 */
q = ((q ) + i) >> 4; /* times 0.00011001101 */
/* compute the reimainder as r = i - 10*q */
r = ((q<<2) + q) << 1; /* times 1010. */
r = i - r;
}
The particular choice of one or the other of these schemes can only be made after compiling them or hand translation to machine code. Depending on the specific features offered by the target architecture, either of the above may be the fastest or most compact, and careful use of small optimizations may tilt the balance one way or the other.
Depending on the space-time tradeoffs of the application, the above code may be expanded in-line as an open macro, or it may be called as a closed function. If in-line expansion is appropriate, it should be noted that the computations of c 3 and c 4 involve dividends no greater than 65. For dividends up to 68, the multiplier 0.0001101 gives exact results, suggesting the following version of the print routine:
void putdec( short int n )
{
unsigned char d4, d3, d2, d1, d0, q;
if (n < 0) {
putchar( '-' );
n = -n;
}
d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12) & 0xF;
d0 = 6*(d3 + d2 + d1) + (n & 0xF);
q = (d0 * 0xCD) >> 11;
d0 = d0 - 10*q;
d1 = q + 9*d3 + 5*d2 + d1;
q = (d1 * 0xCD) >> 11;
d1 = d1 - 10*q;
d2 = q + 2*d2;
q = (d2 * 0x1A) >> 8;
d2 = d2 - 10*q;
d3 = q + 4*d3;
d4 = (d3 * 0x1A) >> 8;
d3 = d3 - 10*d4;
putchar( d4 + '0' );
putchar( d3 + '0' );
putchar( d2 + '0' );
putchar( d1 + '0' );
putchar( d0 + '0' );
}
All multiplications in the above code can be reduced to short sequences of shift and add instructions, and it is straightforward to add the code discussed earlier to suppress leading zeros from this code.
All of these details are incorporated into the attached
Thanks to Mark Ramsey, who, on January 22, 2007 pointed out two small typos with big consequences in the section on Living Within 8 Bits .
Thanks to Dennis Vlasenko, who, on June 15, 2007 pointed out more typos in the section on Doing Without Multiply and Divide .
Thanks to Joe Zbiciak, who, on August 23, 2007 pointed out a small error the introduction