Solved

unsigned 6-bit integer division ?

Posted on 2009-05-01
559 Views
i am trying to divide 50 by 23 . These are unsigned 6-bit integers.

50 = 00110010
23 = 00010111

since numbers are 6 bits there are 7 steps.

after the 6th step R=R-D since result is not negative remainder becomes 000100 and
quotient = 0001 , divisor - 101110 (before shifted to right). I don't know what to do next
I'm not sure whether i am doing it right way. Can someone explain this?

Thanks
0
Question by:emreayman

LVL 84

Expert Comment

How did you get to that step?
0

LVL 20

Expert Comment

What algorithm do you use?
0

Author Comment

0

LVL 20

Accepted Solution

The trick is that you need to normalize the numbers properly before starting the division. Starting with the numbers naively results in garbage -- see below.
Compare the example in the text book on page 186: the 4 bit divisor is scaled by shifting it left 4 bits initially.
``````Wrong:

=====

At START:  R = 00110010  D = 00010111  Q = 00000000

After 1:   R = 00011011  D = 00010111  Q = 00000000

After 2a:  R = 00011011  D = 00010111  Q = 00000001

After 3:   R = 00011011  D = 00001011  Q = 00000001

After 1:   R = 00010000  D = 00001011  Q = 00000001

After 2a:  R = 00010000  D = 00001011  Q = 00000011

After 3:   R = 00010000  D = 00000101  Q = 00000011

After 1:   R = 00001011  D = 00000101  Q = 00000011

After 2a:  R = 00001011  D = 00000101  Q = 00000111

After 3:   R = 00001011  D = 00000010  Q = 00000111

After 1:   R = 00001001  D = 00000010  Q = 00000111

After 2a:  R = 00001001  D = 00000010  Q = 00001111

After 3:   R = 00001001  D = 00000001  Q = 00001111

After 1:   R = 00001000  D = 00000001  Q = 00001111

After 2a:  R = 00001000  D = 00000001  Q = 00011111

After 3:   R = 00001000  D = 00000000  Q = 00011111

After 1:   R = 00001000  D = 00000000  Q = 00011111

After 2a:  R = 00001000  D = 00000000  Q = 00111111

After 3:   R = 00001000  D = 00000000  Q = 00111111

After 1:   R = 00001000  D = 00000000  Q = 00111111

After 2a:  R = 00001000  D = 00000000  Q = 01111111

After 3:   R = 00001000  D = 00000000  Q = 01111111

After 1:   R = 00001000  D = 00000000  Q = 01111111

After 2a:  R = 00001000  D = 00000000  Q = 11111111

After 3:   R = 00001000  D = 00000000  Q = 11111111

Hence the result of the program is:

"50 / 23 is  -1 remainder 8" -- not very promising

RIGHT:

=====

At START:  R = 000000 110010  D = 010111 000000  Q = 000000 000000

first round:

After 1:   R < 0

After 2b:  R = 110010  D = 010111 000000  Q = 000000

After 3:   R = 110010  D = 001011 100000  Q = 000000

second round:

After 1:   R < 0

...

After 3:   R = 110010  D = 000000 101110  Q = 000000

sixth round:

After 1:   R = 000100  D = 000000 101110  Q = 000000

After 2a:  R = 000100  D = 101110  Q = 000001

After 3:   R = 000100  D = 010111  Q = 000001

seventh round:

After 1:   R < 0

After 2b:  R = 000100  D = 010111  Q = 000010

After 3:   R = 000100  D = 001011  Q = 000010

END

Now the result is "50 / 23 is 2 remainder 4" as expected
``````
0

Author Comment

Thank you. I have another question. how can i divide 25 by 44. since the quotient will never be 1. how can i calculate it using same algorithm?
0

Featured Post

This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
Internet Business Fax to Email Made Easy - With eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, fr…