64 位/64 位余数查找算法在 32 位处理器上？

Question

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

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;
}

还是我错过了这里的船？

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

Answer 2

这是一个除法算法，运行 in O(log(n/d))

uint64_t slow_division(uint64_t n, uint64_t d)
{
   uint64_t i = d;
   uint64_t q = 0;
   uint64_t r = n;
   while (n > i && (i >> 63) == 0) i <<= 1;
   while (i >= d) {
      q <<= 1;
      if (r >= i) { r -= i; q += 1; }
      i >>= 1;
   }
   // quotient is q, remainder is r 
   return q;    // return r 
}

q（商）如果只需要 r（余数）可以去掉。您可以将每个中间变量 i、q、r 实现为一对 uint32_t，例如i_lo, i_hi, q_lo, q_hi .....移位，加减lo和hi都是简单的操作。

#define left_shift1 (a_hi, a_lo)          // a <<= 1    
{
    a_hi = (a_hi << 1) | (a_lo  >> 31)
    a_lo = (a_lo << 1) 
}

#define subtraction (a_hi, a_lo, b_hi, b_lo)    // a-= b    
{
    uint32_t t = a_lo
    a_lo -= b_lo
    t = (a_lo > t)        // borrow
    a_hi -= b_hi + t
}   

#define right_shift63 (a_hi, a_lo)      // a >> 63
{
   a_lo = a_hi >> 31;
   a_hi = 0;
}

等等。

0 作为除数仍然是一个未解决的挑战 :-) .

64 位/64 位余数查找算法在 32 位处理器上？

64 bit / 64 bit remainder finding algorithm on a 32 bit processor?

c

algorithm

arm

integer-division

eabi