In C,
the divisor and divided are both 64bit integer that are consist of two 32int, hi, lo
and the quotient is also 64 bit that is consist of hi and lo.
i cant use float and long long data type only int32.
i tried it by compare divisor and higher bit of divided and subtract if divisor bigger and shift right way. (like this picture Improved binary division algorithm in MIPS )
but it is too slow..... i needs 64cycle
Remember how you learned to do long division is school?
Just like that but count up to 64K in each "digit"
If you only have 32-bit operations available, then you need 2 "digits" to perform each multiply or divide and get a value and a remainder, so you make your digits 16-bit, 64K.
[Note that some processors, don't have a 64x64=>64bit or 64/64=>64bit operation available but do have a 32x32=>64 and 64/32=>32r32 operation, but it will be difficult to coerce the C compiler to generate these instructions.]
I'm going to let you work out the details... If need be do it in decimal first with 4 digits dividend and divisor.
You can see that it turns into a lot of multiply and divide operations, compared to a simple 32-bit divide.
If you just want an approximation then you could just shift down both 64-bit values until the dividend is less than 32-bit.
Slightly more accurate is to shift both the divisor and dividend to 32-bit, and remember the number of bits shifted for each, do the division, then re-apply the shifts.
You can use this approximate result to make a better result. Multiply the original divisor by the result, and compare that with your original dividend. If it is too high, try subtracting the divisor just once. If it is too low try adding the divisor just once. If that gets the better result decrement or increment your answer as appropriate.
