1

我知道过去曾提出过类似的问题，但经过漫长的过程，我已经实现了算法，以使用重复减法除法正确找到商。但我无法从这种方法中找出其余部分。是否有任何快速简便的方法可以在 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

4

2 回答 2

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

还是我错过了船，在这里？

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

于 2017-05-23T07:56:11.823 回答
1

这是一个除法算法，运行时间为 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 
}

如果您只需要 r（余数），则可以删除 q（商）。您可以将每个中间变量 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 作为除数仍然是一个未解决的挑战:-)。

于 2017-11-30T19:50:08.457 回答