This application note presents programming techniques for performing commonly found radix (base) conversions.
If you go to school, they will tell you: "An efficient technique for binarytoBCD conversion is that of the so called ADD3 algorithm, and will convert the original binary number into three BCD digits (HUNDREDS, TENS, UNITS)." The algorithm can be expressed as follows:
1. Set HUNDREDS=0, TENS=0, UNITS=0, COUNT=8.
2. If any BCD digit is 5 or greater, add three to that digit.
3. Decrement COUNT and shift left. The bit shifted from the 8 bit binary is carried into UNITS, the bit shifted from UNITS is carried to TENS, etc.
4. If count not equal to 0, to step 2, else STOP.
Example:
HUNDREDS 
TENS 
UNITS 
BINARY 

0000 
0000 
0000 
1111 
1111  Start 
0000 
0000 
0001 
1111 
1110  Shift 1 
0000 
0000 
0011 
1111 
1100  Shift 2 
0000 
0000 
0111 
1111 
1000  Shift 3 
0000 
0000 
1010 
1111 
0000  ADD3 to UNITS 
0000 
0001 
0101 
1111 
0000  Shift 4 
0000 
0001 
1000 
1111 
0000  ADD3 to UNITS 
0000 
0011 
0001 
1110 
0000  Shift 5 
0000 
0110 
0011 
1100 
0000  Shift 6 
0000 
1001 
0011 
1100 
0000  ADD3 to TENS 
0001 
0010 
0111 
1000 
0000  Shift 7 
0001 
0010 
1010 
1000 
0000  ADD3 to UNITS 
0010 
0101 
0101 
0000 
0000  Shift 8 
Result 1111 1111_{2} = FF_{16} = 255_{10 }
Thank goodness none of these routines do that.
From: Ken Mathis
;Purpose: Convert an 8 bit number to BCD ;so value can be sent to a 7447 seven segment display driver ;I/O pin hungry, requires 8 bits to send data out. ;temp1 holds binary value ;BCD result in temp1 ;$32 (50 decimal) becomes or %01010000 hex_to_bcd clr temp0 ;clear register convert inc temp0 ;increment number of 10’s mov w,#$0A sub temp1,w ;subtract 10 from temp1 snc ;skip next instruction if underflow occurs jmp convert ;repeat mov w,#$A add temp1,w ;restore temp1. number of 1’s after restored dec temp0 ;correction to the number of 10’s swap temp0 ;swap upper and lower nibble of temp0 add temp1,temp0 ;place number of 10’s in upper nibble of temp1 ret ;temp1 now hold BCD value of $32
Binary to BCD halfpacked 8 bit to 3 digit
From: Scott Dattalo, notes
Translated and optimized for the Ubicom SX by Nikolai Golovchenko
;******************************** ;binary_to_bcd  8bits ; ;Input ; bin  8bit binary number ; A_{1}*16+A_{0} ;Outputs ; hundreds  the hundreds digit of the BCD conversion ; tens_and_ones  the tens and ones digits of the BCD conversion binary_to_bcd: clr hundreds mov W, <>bin ;w = A_{0}*16+A_{1} add W, bin ;w = A_{0}+A_{1} and W, #00001111b ;w = A_{0}+A_{1} % 16 mov tens_and_ones, W ;tens_and_ones = A_{0}+A_{1} % 16 mov W, #$16 snb DC ;if A_{0}+A_{1} > 16 add tens_and_ones, W ; tens_and_ones += 16 mov W, #$06 snb DC ;if tens_and_ones % 16 > 10 add tens_and_ones, W ; tens_and_ones += 6 add tens_and_ones, W ;tens_and_ones += 6 sb DC ;if tens_and_ones < 10 sub tens_and_ones, W ; tens_and_ones = 6 mov W, #$16  1 + $6 snb bin.4 add tens_and_ones, W mov W, #$06 sb DC add tens_and_ones, W mov W, #$30 snb bin.5 add tens_and_ones, W mov W, #$20 snb bin.7 add tens_and_ones, W mov W, #$60 snb bin.6 add tens_and_ones, W add tens_and_ones, W rl hundreds sb hundreds.0 sub tens_and_ones, W snb bin.7 inc hundreds
Notes from Scott Dattalo on converting a Byte to BCD quickly:
[The routine I have implemented is] based on binary comparisons. It takes advantage of this little trick to quickly ascertain the ones' digit:If you look at the ones' digit for 2^N you see this pattern: n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11 ... 2^n % 10 = 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8 ... 2^n in hex = 0, 2, 4, 8,10,20,40,80, ...If it wasn't for the annoying 6's, you could simply sum the nibbles to get and get the ones' digit (after a relatively simple binary to BCD conversion). For example, the ones' digit for 2^5 = 0x20 is 2 (because 0x20 = 32 decimal). This sumofdigits trick works even if the binary number is not a perfect power of 2.
For example, consider 0xef:0xef = 239 base 10, the one's digit is '9' 0xe + 0xf = 0x1dA binary to bcd conversion of 0x1d yields 0x29 (because 1d hex is 29 decimal). And the one's digit is '9', just like the one's digit of 0xef.
Now, this trick only works if bit 4 is not set. (notice my contrived example has every bit set except for that one). It's simple enough to test if bit 4, (and bit 8 for 16bit conversions) and to subtract 1 and then add 6 (or simply add 5) if it is.
The second observation is that the sum of all of the tens' digits of 2^n (for n<8) is less than 16, and thus can fit into one nibble. This simplifies having to deal with overflow until after all of the digits have been added together. (What I'm saying is simply that if you look at the eight 2^n numbers 1,2,4,8,0x10,0x20,0x40,0x80 and sum all of the upper nibbles together: 0x10 + 0x20 + 0x40 + 0x80 you get 0xf0 which doesn't cause a carry.)
The third observation is that the BCD result is greater than 200 only if the most significant bit is set. Note, that this is necessary but not sufficient condition. e.g. 0x80 has the msb set, but is only 128, but 200 is 0xc8.
From: TakeThisOuTwunnerful1 at TakeThisOuTmsn.com
conv_high, mid and low contain the converted BCD components of a single $byte; the_val is the input value containing the hexadecimal value to be converted. #hundreds = #100 #tens = #10 #ones = #1 bcd_conv clr conv_low zero out temp storage for new conversion clr conv_mid clr conv_high hun stc ;set carry flag for test sub the_val,#hundreds ;subtract and check flag jnc ten ; if =0, done with hundreds conversion inc conv_high ;carry is set, so inc high bcd byte jmp hun ;check again to see if over 200 in value ten clc ;clear carry first (carryx) add the_val,#hundreds ;need to correct for underrun first ten_a stc ;set carry flag for test sub the_val,#tens ;subtract and check flag jnc one ; if =0, done with tens conversion inc conv_mid ;carry is set, so inc middle bcd byte jmp ten_a ;check again to see if any more 10s value one clc ;clear carry first (carryx) add the_val,#tens ;correct for underrun but in tens now. one_a stc ;set carry flag for test sub the_val,#ones ;subtract and check flag jnc ascii_correct ;if =0, done with 1s conversionprepare for ascii inc conv_low ;carry is set, so inc low bcd byte jmp one_a ;check again to see if any 1s left in value ascii_correct clc ;adds $30 to each bcd digit for correct output to lcd add conv_high,#$30 ;now should display on lcd correctly clc ;since carryx, clear c add conv_mid,#$30 clc add conv_low,#$30 clc ;house cleaning clear the carry clz ;clear the zero flag
From: John Payson via Scott Dattalo
[ed: quick guess at speed is that about 200 instructions will be executed and 50 instructions + 7 registers used]
;Takes hex number in NumH:NumL Returns decimal in ;TenK:Thou:Hund:Tens:Ones ;written by John Payson ;input ;=A_{3}*16^{3} + A_{2}*16^{2} + A_{1}*16^{1} + A_{0}*16^{0} ;=A_{3}*4096 + A_{2}*256 + A_{1}*16 + A_{0} NumH DS 1 ;A3*16+A2 NumL DS 1 ;A1*16+A0 ;output ;=B_{4}*10^{4} + B_{3}*10^{3} + B_{2}*10^{2} + B_{1}*10^{1} + B_{0}*10^{0} ;=B_{4}*10000 + B_{3}*1000 + B_{2}*100 + B_{1}*10 + B_{0} TenK DS 1 ;B_{4} Thou DS 1 ;B_{3} Hund DS 1 ;B_{2} Tens DS 1 ;B_{1} Ones DS 1 ;B_{0} mov W, <>NumH ;w = A_{2}*16+A_{3} or W, #$F0 ;w = A_{3}16 mov Thou, W ;B_{3} = A_{3}16 add Thou, W ;B_{3} = 2*(A_{3}16) = 2A_{3}  32 mov Hund, W mov W, #$E2 add Hund, W ;B_{2} = A_{3}16  30 = A_{3}46 mov W, #$32 add W, Hund mov Ones, W ;B_{0} = A_{3}46 + 50 = A_{3}+4 mov W, NumH ;w = A_{3}*16+A_{2} and W, #$0F ;w = A_{2} add Hund, W ;B_{2} = A_{3}46 + A_{2} = A_{3}+A_{2}46 add Hund, W ;B_{2} = A_{3}+A_{2}46 + A_{2} = A_{3}+2A_{2}46 add Ones, W ;B_{0} = A_{3}+4 + A_{2} = A_{3}+A_{2}+4 mov Tens, W mov W, #$E9 add Tens, W ;B_{1} = A_{2}23 mov W, Tens add Tens, W ;B_{1} = 2*(A_{2}23) add Tens, W ;B_{1} = 3*(A_{2}23) = 3A_{2}69 (Doh! thanks NG) mov W, <>NumL ;w = A_{0}*16+A_{1} and W, #$0F ;w = A_{1} add Tens, W ;B_{1} = 3A_{2}69 + A_{1} = 3A_{2}+A_{1}69 range 69...9 add Ones, W ;B_{0} = A_{3}+A_{2}+4 + A_{1} = A_{3}+A_{2}+A_{1}+4 and Carry = 0 (thanks NG) rl Tens ;B_{1} = 2*(3A_{2}+A_{1}69) + C = 6A_{2}+2A_{1}138 and Carry is now 1 as tens register had to be negative rl Ones ;B_{0} = 2*(A_{3}+A_{2}+A_{1}+4) + C = 2A_{3}+2A_{2}+2A_{1}+9 (+9 not +8 due to the carry from prev line, Thanks NG) not Ones ;B_{0} = ~(2A_{3}+2A_{2}+2A_{1}+9) = 2A_{3}2A_{2}2A_{1}10 (ones complement plus 1 is twos complement. Thanks SD) ;;Nikolai Golovchenko [golovchenko at MAIL.RU] says: complement [not Ones] can be regarded like: ;; not Ones ;; inc Ones ;; dec Ones ;;First two instructions make up negation. So, ;;Ones = Ones  1 ;; =  2 * (A3 + A2 + A1)  9  1 ;; =  2 * (A3 + A2 + A1)  10 rl Ones ;B_{0} = 2*(2A_{3}2A_{2}2A_{1}10) = 4A_{3}4A_{2}4A_{1}20 mov W, NumL ;w = A_{1}*16+A_{0} and W, #$0F ;w = A_{0} add Ones, W ;B_{0} = 4A_{3}4A_{2}4A_{1}20 + A_{0} = A_{0}4(A_{3}+A_{2}+A_{1})20 range 215...5 Carry=0 rl Thou ;B_{3} = 2*(2A_{3}  32) = 4A_{3}  64 mov W, #$07 ;w = 7 mov TenK, W ;B_{4} = 7 ;B_{0} = A_{0}4(A_{3}+A_{2}+A_{1})20, 5...200 ;B_{1} = 6A_{2}+2A_{1}138, 18...138 ;B_{2} = A_{3}+2A_{2}46, 1...46 ;B_{3} = 4A_{3}64, 4...64 ;B_{4} = 7, 7 ; At this point, the original number is ; equal to TenK*10000+Thou*1000+Hund*100+Tens*10+Ones ; if those entities are regarded as two's compliment ; binary. To be precise, all of them are negative ; except TenK. Now the number needs to be normal ; ized, but this can all be done with simple byte ; arithmetic. mov W, #$0A ;w = 10 Lb1: ;do add Ones, W ; B_{0} += 10 dec Tens ; B_{1} = 1 sb 3.0 ;skip no carry jmp Lb1 ; while B_{0} < 0 ;jmp carry Lb2: ;do add Tens, W ; B_{1} += 10 dec Hund ; B_{2} = 1 sb 3.0 jmp Lb2 ; while B_{1} < 0 Lb3: ;do add Hund, W ; B_{2} += 10 dec Thou ; B_{3} = 1 sb 3.0 jmp Lb3 ; while B_{2} < 0 Lb4: ;do add Thou, W ; B_{3} += 10 dec TenK ; B_{4} = 1 sb 3.0 jmp Lb4 ; while B_{3} < 0 ret
A few notes (stolen shamelessly from Scott Dattalos' website) on how this works: Please take a preemptive asprin before reading. <GRIN>
If you have a 4 digit hexadecimal number, it may be written as N = a_3*16^3 + a_2*16^2 + a_1*16 + a_0 where a_i, i=0,1,2,3 are the four hexadecimal digits. If you wish to convert this to decimal, then you need to express N as N = b_4*10^4 + b_3*10^3 + b_2*10^2 + b_1*10 + b_0 Where b_j, j=0,1,2,3,4 are the five decimal digits. The reason there are 5 digits in the decimal representation is because the maximum four digit hexadecimal number (0xffff) requires 5 decimal digits (65535). Now the goal is to find a set of equations that allow the b_j's to be expressed in terms of the a_i's. There are infinitely many ways to do this. Here are two of probably the simplest expressions. First, expand the 16^i's and then collect all coefficients of the 10^j's: N = a_3*4096 + a_2*256 + a_1*16 + a_0 = a_3*4*10^3 + a_2*2*10^2 + (a_3*9 + a_2*5 + a_1)*10 + 6*(a_3 + a_2 + a_1) + a_0 This gives us five equations: b_0 = 6*(a_3 + a_2 + a_1) + a_0 b_1 = a_3*9 + a_2*5 + a_1 b_2 = 2*a_2 b_3 = 4*a_3 b_4 = 0 Which as John says, must be "normalized". Normalization in this context means we need to reduce the b_j's such that 0 <= b_j <= 9 In other words we need to find: c_0 = b_0 mod 10 b_1 = (b_1 + (b_0  c_0)/10) c_1 = b_1 mod 10 b_2 = (b_2 + (b_1  c_1)/10) c_2 = b_2 mod 10 b_3 = (b_3 + (b_2  c_2)/10) c_3 = b_3 mod 10 c_4 = (b_4 + (b_3  c_3)/10) mod 10 = (b_2  c_2)/10 Division by 10 can be done quite efficiently (as was shown in another thread several months ago). However, it does require a significant amount of code space compared to say repeated subtractions. Unfortunately, there can be very many subtractions that are required. For example, b_1 could be as large as 15*16, or 240. 10 would have to be subtracted 24 times if you wish to compute 240 mod 10. I presume John realized this inefficiency and thus sought to express N so that repeated subtractions could be used and that the total number of subtractions are minimized. This leads to the next way that N can be expressed: N = a_3*(4100  4) + a_2*(260  4) + a_1*(204) + a_0 = 4*a_3*10^3 + (a_3 + 2*a_2)*10^2 + (6*a_2 + 2*a_1)*10 + a_0  4*(a_3 + a_2 + a_1) This gives five new equations for the b_j's. b_0 = a_0  4*(a_3 + a_2 + a_1) b_1 = 6*a_2 + 2*a_1 b_2 = a_3 + 2*a_2 b_3 = 4*a_3 b_4 = 0 However, these equations are still not conducive to the repeated subtraction algorithm, at least the way John has done it. In other words, it is possible to precondition each of the b_j's so that they are less than zero. Then the repeated subtractions can simultaneously perform the "mod 10" and "/10" operations shown above. Consider the equation b_0 for example, b_0 = a_0  4*(a_3 + a_2 + a_1) Since each a_i must satisfy: 0 <= a_i <= 15, then b_0 ranges: 60 <= b_0 <= 15 We can make b_0 negative by subtracting any number greater than 15. A logical choice is 20. This is because if we subtract 20 from b_0, we can add 2 to b_1 to keep the net result the same. The reason we add "2" can be seen: b_1*10 + b_0 = b_1*10 + b_0 + 20  20 = (b_1 + 2)*10 + b_0  20 Carrying this concept out for the rest of the b_i's we have. b_0 = a_0  4*(a_3 + a_2 + a_1)  20 b_1 = 6*a_2 + 2*a_1 + 2  140 = 6*a_2 + 2*a_1  138 b_2 = a_3 + 2*a_2 + 14  60 = a_3 + 2*a_2  46 b_3 = 4*a_3 + 6  70 = 4*a_3  64 b_4 = 0 + 7 = 7 And if you look at John's code closely, you will see this is how he has expressed the b_j's.
As you can see, there are many ways to "skin the cat" and most of the time someone else has taken the time and has the education to find the better way. Learning from others is a "good thing" and a wonderful way to justify higher education; especially math.
Here are some tables of decimal and binary "hotspots." Can you see a pattern?
Decimal  Binary 

60000  001110101001100000 
50000  001100001101010000 
40000  001001110001000000 
30000  111010100110000 
20000  100111000100000 
10000  010011100010000 
9000  010001100101000 
8000  001111101000000 
7000  001101101011000 
6000  001011101110000 
5000  001001110001000 
4000  111110100000 
3000  101110111000 
2000  011111010000 
1000  001111101000 
900  001110000100 
800  001100100000 
700  001010111100 
600  001001011000 
500  111110100 
400  110010000 
300  100101100 
200  011001000 
100  001100100 
90  001011010 
80  001010000 
70  001000110 
60  111100 
50  110010 
40  101000 
30  011110 
20  010100 
10  001010 
Decimal  Binary 

59999  001110101001011111 
49999  001100001101001111 
39999  001001110000111111 
29999  111010100101111 
19999  100111000011111 
9999  010011100001111 
8999  010001100100111 
7999  001111100111111 
6999  001101101010111 
5999  001011101101111 
4999  001001110000111 
3999  111110011111 
2999  101110110111 
1999  011111001111 
999  001111100111 
899  001110000011 
799  001100011111 
699  001010111011 
599  001001010111 
499  111110011 
399  110001111 
299  100101011 
199  011000111 
99  001100011 
89  001011001 
79  001001111 
69  001000101 
59  111011 
49  110001 
39  100111 
29  011101 
19  010011 
9  001001 
Decimal  Binary 

60000  001110101001100000 
59999  001110101001011111 
50000  001100001101010000 
49999  001100001101001111 
40000  001001110001000000 
39999  001001110000111111 
30000  111010100110000 
29999  111010100101111 
20000  100111000100000 
19999  100111000011111 
10000  010011100010000 
9999  010011100001111 
9000  010001100101000 
8999  010001100100111 
8000  001111101000000 
7999  001111100111111 
7000  001101101011000 
6999  001101101010111 
6000  001011101110000 
5999  001011101101111 
5000  001001110001000 
4999  001001110000111 
4000  111110100000 
3999  111110011111 
3000  101110111000 
2999  101110110111 
2000  011111010000 
1999  011111001111 
1000  001111101000 
999  001111100111 
900  001110000100 
899  001110000011 
800  001100100000 
799  001100011111 
700  001010111100 
699  001010111011 
600  001001011000 
599  001001010111 
500  111110100 
499  111110011 
400  110010000 
399  110001111 
300  100101100 
299  100101011 
200  011001000 
199  011000111 
100  001100100 
99  001100011 
90  001011010 
89  001011001 
80  001010000 
79  001001111 
70  001000110 
69  001000101 
60  111100 
59  111011 
50  110010 
49  110001 
40  101000 
39  100111 
30  011110 
29  011101 
20  010100 
19  010011 
10  001010 
9  001001 
Code:
See also:
file: /Techref/new/letter/news0306.htm, 33KB, , updated: 2006/2/27 09:20, local time: 2020/10/31 12:52,

©2020 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions? <A HREF="http://www.massmind.org/techref/new/letter/news0306.htm"> June 2003 SXList.com newsletter  SX radix routines</A> 
Did you find what you needed? 
Welcome to massmind.org! 
Welcome to www.massmind.org! 
.