64-bit to 32-bit division

Question

I am looking for a quick way to do the following divison:

• A dividend is a signed 64-bit integer.
• Divisor is a signed 32-bit integer.
• Quotient must be a signed 64-bit integer, no remainder needed.
• The low dword of the dividend is zero.

I use only 32-bit data types, since 64-bit ones are poorly supported by the compiler and are not built. Accuracy can be compromised in favor of speed.

Any pointers on this?

Answer 1

64/32 division is supported directly by i386 and possibly by other machines if the high dividend word is smaller than the divider (i.e. the dividend is in the range 32x32-> 64, multiplied by the divider) If your compiler has minimal support for 64- bit types, he can recognize this situation and take advantage of it.

Assuming that you have already checked the generated asm and found that it does not use this, or if you know that your processor does not have such a split instruction, you just need to do a long division, as you learned in class school .. except that she is base-4294967296 instead of base-10.

You can try reading the libgcc source, as it contains code for 64/64 separation for machines that do not have built-in support.

Edit: Actually, since you don't have a 64/32 split operation, you can use base-65536. This is due to the fact that a naive long division requires dividing a "two-digit" number by a "1-digit" number at each step. Of course, now you are stuck taking more steps.