c - 32 位处理器上的 64 位/64 位余数查找算法？

Question

我知道过去曾问过类似的问题，但经过漫长的过程后，我实现了使用重复减法除法正确找到商的算法。但是我无法从这种方法中找出剩余部分。有什么快速简便的方法可以在 32 位处理器上找出 64 位/64 位除法中的余数。更准确地说，我正在尝试实现

ulldiv_t __aeabi_uldivmod(  
 unsigned long long n, unsigned long long d)  

本文档中引用 http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf

Answer 1

什么？如果你重复做减法(这听起来很基础)，那么当你不能做另一个减法时，剩下的不就是余数吗？

至少这是天真的直观方式:

uint64_t simple_divmod(uint64_t n, uint64_t d)
{
  if (n == 0 || d == 0)
    return 0;
  uint64_t q = 0;
  while (n >= d)
  {
    ++q;
    n -= d;
  }
  return n;
}

还是我错过了这里的船？

当然，对于大数来说这会非常慢，但这是重复的减法。我确信(即使不看!)还有更高级的算法。