The double-dabble algorithm, performed on the value 243, looks like this:
0000 0000 0000 11110011 Initialization
0000 0000 0001 11100110 Shift
0000 0000 0011 11001100 Shift
0000 0000 0111 10011000 Shift
0000 0000 1010 10011000 Add 3 to ONES, since it was 7
0000 0001 0101 00110000 Shift
0000 0001 1000 00110000 Add 3 to ONES, since it was 5
0000 0011 0000 01100000 Shift
0000 0110 0000 11000000 Shift
0000 1001 0000 11000000 Add 3 to TENS, since it was 6
0001 0010 0001 10000000 Shift
0010 0100 0011 00000000 Shift
Now do the number 255 in binary...
0000 0000 0000 11111111 start
0000 0000 0001 11111110 shift
0000 0000 0011 11111100 shift
0000 0000 0111 11111000 shift
0000 0000 1010 11111000 added 3 since ones was 7 (and 7>4)
0000 0001 0101 11110000 shift
0000 0001 1000 11110000 added 3
0000 0011 0001 11100000 shift
0000 0110 0011 11000000 shift
0000 1001 0011 11000000 added 3 to tens
0001 0010 0111 10000000 shift
0001 0010 1010 10000000 added 3
0010 0101 0101 00000000 shift
done.
In-place algo for the binary number 1023:
(this is a bit harder to determine when to add 3)
INDEX THOU HUND TENS UNITS
0 11 1111 1111 x000 Start
1 11 1111 111x 0001 Shift 1
2 11 1111 11x0 0011 Shift 2
3 11 1111 1x00 0111 Shift 3
4 11 1111 1x00 1010 ADD-3 to UNITS
4 11 1111 x001 0101 Shift 4
5 11 1111 x001 1000 ADD-3 to UNITS
5 11 111x 0011 0001 Shift 5
6 11 11x0 0110 0011 Shift 6
7 11 11x0 1001 0011 ADD-3 to TENS (live)
7 11 1x01 0010 0111 Shift 7
8 11 1x01 0010 1010 ADD-3 to UNITS
8 11 x010 0101 0101 Shift 8
9 11 x010 0101 1000 ADD-3 to UNITS
9 11 x010 1000 1000 ADD-3 to TENS <--
9 1x 0101 0001 0001 Shift 9
10 1x 1000 0001 0001 ADD-3 to HUND <--
10 x1 0000 0010 0011 Shift 10
If Mr Al's explanation went straight over your head....
Binary Code Decimal...
Example
lets take a number... decimal 23.
23 decimal is 17 hex and 00010111 binary.
Now the conversion.
23 modulus 10 = 3 ( save the 3 )
23 divided by 10 = 2 then 2 multiplied by 16 = 32
add the modulus result 32 + 3 = 35
35 decimal is 23 hex... BCD is 23
the couple of masks are only there to ensure you are working with the nibble only..
going back is the reverse..
23 hex.. (BCD )
23 take the lower nibble 3 ( save the 3 )
23 divide by 16 = 2 then 2 multiplied by 10 = 20
We now have 0x17 hex which is 23 decimal..
I don't know why MikroC uses int's when we are clearly using unsigned char's..
´Hi,
A multiplication by 16 can be done using four left shifts.
For example if you start with binary (decimal):
0000 0001 (1)
and shift it left once you get:
0000 0010 (2)
and shift it left again you get:
0000 0100 (4)
and shift it left again:
0000 1000 (8)
and shift it left one last time:
0001 0000 (16)
so we managed to multiply 1 times 16 using just 4 shifts.
If we shift to the right four times instead of to the left four times we do an integer divide by 16, which means we divide by 16 but loose any fractional part.
´
Concise and to the point. I like the way!
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?