Hello there,

I made a simple hex calculator recently because i needed one for some large hex numbers mostly, and it also does some binary stuff. For example, it can turn a very large hex number like:
0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF
into BCD or if you want to call it just a 'decimal' number. The number is then converted to string for display.

What it does NOT have yet, is a BCD to binary (or hex) converter, and i found that it would be convenient to have this also. This would take a decimal (or BCD as it is called also) number like this:
341001922204623546932120
and convert it into either hex or binary.

There is a catch here though. I dont want to have to create a base 10 number cruncher if i dont have to. To convert BCD to binary a typical technique is to repeatedly divide by 2 to get the binary number. For example, say we have a BCD number "14" and we want to convert to binary. It would go like this:
14/2=7 with remainder r=0, so we write "0",
7/2=3 with r=1 so we write "1",
3/2=1 with r=1, so we write "1",
1/2=0 with r=1, so we write "1",
so the entire conversion is (writing all the results from the bottom up):
1110
which of course is equal to decimal 14.
This is great and fantastic and all that, but what this algorithm requires is a math number cruncher that can work in decimal, at least so it can divide by 2. For example a larger number would require a fully implemented base 10 cruncher for dividing by 2:
9999999999999999/2=4999999999999999, r=1, so first binary digit is '1'.
Note this requires the ability to divide by 2 in base 10, which is not available yet and i would like to avoid this if possible.
What is available:
N digit hex calculations, four banger: add, subtract, multiply, divide.
N digit binary calculations, four banger: add, subtract, multiply, divide.
N digit shifts left or right.
Note again there is no "N digit decimal calculations" of any kind except for values less than 2^16.

So the question here is, does anyone know of any algorithm that can convert BCD to binary (or to hex) without requiring a BCD number cruncher, and hopefully using a hex or binary calculation only?

The numbers will come in as a string such as:
"314529"
and of course this can be converted to BCD no problem by converting each number in turn to end up with:
0011 0001 0100 0101 0010 1001

if that helps at all.

If there is no other way, then maybe your best decimal divide by 2 algorithm.

Hey, thanks

 

Hi,

I am a bit surprised to see that maybe nobody else does this kind of thing either on the computer or in a microcontroller.

Anyway, i found one somewhat easy way to do it. Since i already had a binary number cruncher, doing it all in binary seemed like an idea.

Recognizing that the total value of a BCD number like 987 is just:
9*100+8*10+7

and that 10 decimal in binary is 1010 (or in hex A) and 100 decimal in binary is just 1010*1010 (or in hex A*A) if i start with a multiplier M=0001 binary and increase this by multiplying by 1010 binary for each digit going from right to left, it would just be a matter of multiplying by the next digit and then adding the result to the final result, then increasing the multiplier again by a factor of 1010 binary. So the number 255 which in BCD would look like 0010 0101 0101 would go like this:
M=0001
Sum=0
0101*M=0101, Sum=Sum+0101=0101
M=M*1010=1010
0101*M=110010, Sum=Sum+110010=0101+110010=110111
M=M*1010=1100100
0010*M=11001000, Sum=Sum+11001000=110111+11001000=11111111

and this last result is equal to 255 decimal, the required result.
So it's just a matter of doing some multiplications and additions and they can all be done in binary so the final result ends up being in binary too, the desired end result format.

It would still be interesting to see other routines, or a nice decimal divide by 2 routine.

 

So the question here is, does anyone know of any algorithm that can convert BCD to binary (or to hex) without requiring a BCD number cruncher, and hopefully using a hex or binary calculation only?

The way I've always done it goes something like this:

1. Allocate a binary variable sufficiently large to hold the result, and initialize it to zero
2. Initialize a pointer to point to the most significant BCD digit
3. Read the BCD digit addressed by the pointer and add it to the result variable
4. If that was the least significant BCD digit, quit; otherwise,
5. Advance the pointer to point to the next most significant BCD digit
6. Multiply the result variable by 10 (0x000A)
7. Go back to step 3.

 

Hi,

Sounds good

 

Repeated division by the number base you are converting to -- i.e., the method you describe in your first post -- requires the math to be done in the number base you are converting from. So, for humans, this is good for converting from decimal to some other base. Repeated multiplication by the number base you are converting from requires the math to be done in the number base you are converting to. So, for humans, this is good for converting to decimal from some other base. But if you want to convert from base-10 to base-2 and do the math in base-2, then all you need to do is use repeated multiplication. This is basically the result you and OBW are talking about in the last two posts. This might help you see the internals a bit better.

Consider a four-digit binary number with digits A, B, C, and D written as ABCD. While this can most basically be written as

A*1000 + B*100 + C *10 + D

It can also be written as

((A*10 + B)*10 + C)*10 + D

Which leads to a very simple implementation (namely OBW's algorithm).

 

Hi,

Yes thanks, i realize there are similarities between the two algorithms. At first i was thinking i might have to implement a divide by 2 base 10 number routine, so i am happy i did not have to do that.
I also ran into a quick technique for calculating in base 10 using hex calculations which means no base 10 number cruncher needed...even for floating point.

Back years ago when i was working with the Z80 i did a full implementation of a base 10 number cruncher. I cant remember why i needed that now though. I do remember a little of some of that stuff, and also a binary number cruncher. What i liked about the binary system was that square roots are easy to do...much easier than in base 10.
I also needed large floating point numbers with large exponents. Cant remember too well now but the exponent size went way up there...like to 8 digits or something like that. That's a number like 1.234567890123456789012345678901234567890e+12345678
but there was no limit on size of the base.
That was back when all we had in the uP was 8 bit integer math for the most part.

 

I am a bit surprised to see that maybe nobody else does this kind of thing either on the computer or in a microcontroller.

People do it all the time, via a look-up table (if you have lots of flash space) or a piece of code (switch-case for example, if you are tight on space).

You do it on a per byte/digit basis.