以下内容摘自网上 highgear大师的**，写的非常整齐规范，思路清晰，是数制转换原理最经典的范例，供有心者学习时参考。
-----------------------------------------------------------------------------------------------------------------
转换原理以及 C 演示代码， 很容易转到汇编。
The Basic Idea
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 n3, n2, n1 and n0.
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 = 4096 n3 + 256 n2 + 16 n1 + 1 n0
In the same way, if the value of n, expressed in decimal, is d4d3d2d1d0, where each of d4, d3, d2, d1 and d0 are decimal digits, the value of n can be expressed as:
n = 10000 d4 + 1000 d3 + 100 d2 + 10 d1 + 1 d0
Our problem then, is to compute the di from the ni without dealing directly with the larger number n.
To do this, we first note that the factors used in combining the values of ni can themselves be expressed as sums of multiples of powers of 10. Therefore, we can rewrite the original expression as:
n =
n3( 4×1000 + 0×100 + 9×10 + 6×1 ) +
n2( 2×100 + 5×10 + 6×1 ) +
n1( 1×10 + 6×1 ) +
n0( 1×1 )
If distribute the ni over the expressions for each factor, then factor out the multiples of 100, we get the following:
n =
1000 (4n3) +
100 (0n3 + 2n2) +
10 (9n3 + 5n2 + 1n1) +
1 (6n3 + 6n2 + 6n1 + 1n0)
We can use this to arrive at first approximations ai for d3 through d0:
a3 = 4 n3
a2 = 0 n3 + 2 n2
a1 = 9 n3 + 5 n2 + 1 n1
a0 = 6 n3 + 6 n2 + 6 n1 + 1 n0
The values of ai are not proper decimal digits because they are not properly bounded in the range 0 < ai < 9. Instead, given that each of ni is bounded in the range 0 < ni < 15, the ai are bounded as follows:
0 < a3 < 60
0 < a2 < 30
0 < a1 < 225
0 < a0 < 285
This is actually quite promising because a3 through a1 are less than 256 and may therefore be computed using an 8 bit ALU, and even a0 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 n3 becomes 0 < n3 < 8 and we can conclude naively that
0 < a0 < 243
Note that we said n3 < 8 and not n3 < 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 n3 is 8, all of the other ni are zero, so we can assert globally that
0 < a0 < 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 ai.
Given that we have computed the ai, we can push them into the correct ranges by a series of 8-bit divisions and one 9-bit division, as follows:
c1 = a0 / 10
d0 = a0 mod 10
c2 = (a1 + c1) / 10
d1 = (a1 + c1) mod 10
c3 = (a2 + c2) / 10
d2 = (a2 + c2) mod 10
c4 = (a3 + c3) / 10
d3 = (a3 + c3) mod 10
d4 = c4
In the above, the ci terms represent carries propagated from one digit position to the next. The upper bounds on each of the ci can be computed from the bounds given above for the ai:
c1 < 28 [ = 285 / 10 ]
c2 < 25 [ = (28 + 225) / 10 = 253 / 10 ]
c3 < 5 [ = (25 + 30) / 10 = 55 / 10 ]
c4 < 6 [ = (5 + 60) / 10 = 65 / 10 ]
In computing the bound on c2, 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 n3 is 8, the bound on c1 becomes 23 instead of 28.
有 8-bit 硬件除法
void putdec( uint16_t n )
{
uint8_t d4, d3, d2, d1, q;
uint16_t 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' );
}
有 8-bit 硬件乘法：
void putdec( int16_t n )
{
uint8_t 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' );
} |
楼主
标题置顶
标题高亮
来自 2楼
