One clever way to convert binary numbers to BCD notation (binary-coded decimal) is the "double dabble algorithm" wikipedia: double dabble . It can be adapted to convert binary numbers directly to ASCII digits, and to convert binary numbers into other bases. The double dabble algorithm also works for mixed bases -- for example, for converting a binary number of seconds into the decimal digits for days, 10s of hours, hours, 10s of minutes, minutes, 10s of seconds and seconds. (Ask David Cary for details).
Notes from Scott Dattalo on converting a Byte to BCD quickly:
[The routine I have implemented for the PIC uC 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 sum-of-digits 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 = 0x1d
A 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 exampled has every bit set except for that one). It's simple enough to test if bit 4, (and bit 8 for 16-bit 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.
|file: /Techref/method/math/radixs.htm, 5KB, , updated: 2014/4/24 16:29, local time: 2018/5/24 07:00,
|©2018 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://techref.massmind.org/techref/method/math/radixs.htm"> Radix Conversion Methods</A>
|Did you find what you needed?|
Welcome to massmind.org!
Welcome to techref.massmind.org!