64位乘32位除法

uj2*_*uj2 6 c math 64-bit division

我正在寻找一种快速执行以下分区的方法:

  • Dividend是一个带符号的64位整数.
  • 除数是带符号的32位整数.
  • 商数应该是带符号的64位整数,余数是不必要的.
  • 股息的低位为零.

我只使用32位数据类型,因为编译器不支持64位数据类型,也没有汇编.准确度可能会有所偏差,有利于速度.

关于这个的任何指针?

R..*_*R.. 3

i386 和可能的其他机器直接支持 64/32 除法,只要被除数的高位字小于除数(即被除数在 32x32->64 乘以除数的范围内)。如果您的编译器对 64 位类型的支持最低限度,它可能能够识别这种情况并利用它。

假设你已经检查过生成的asm并发现它没有利用这一点,或者如果你知道你的cpu没有这样的除法指令,那么你只需要像你在小学学到的那样进行长除法。只不过它的基数是 4294967296 而不是基数 10。

您可以尝试阅读 的源代码libgcc,因为它包含针对没有本机支持的计算机的 64/64 除法代码。

编辑:实际上,由于您没有 64/32 除法运算,因此您可能需要使用 base-65536。这是因为简单的长除法需要在每一步将“2 位数字”除以“1 位数字”。当然,现在您必须执行更多步骤......

  • Knuth 对长除法进行了讨论,并描述了长除法算法。如果你确实沿着这条路看下去,Knuth 有一个优化,你可以提前离开循环。它很难测试,它只在少数情况下有帮助,可以安全地排除在外。 (2认同)