主页 / user-232

avp's questions

Martin Hope
avp
Asked: 2020-05-28 05:05:26 +0000 UTC
  • 7

在 32 位微处理器上，需要一个函数（高效算法）来获取uint64_t除以 10 的商和余数（与打印一样）。

爬上互联网后，在http://www.hackersdelight.org/divcMore.pdfuint32_t我只发现了与此代码类似的东西（for ）

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - q*10;
    return q + ((r + 6) >> 4);
    // return q + (r > 9);
}

出于我的目的，我将其更改为这样（实际上，我添加了一个运算符q = q + (q >> 32);：

uint64_t divu64_10 (uint64_t n, uint32_t *rem) {
  uint64_t q, r;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q + (q >> 32);
  q = q >> 3;
  r = n - ((q << 3) + (q << 1));
  *rem = r > 9 ? r - 10 : r;

  //  orig: return q + ((r + 6) >> 4);
  return q + (r > 9);
}

我通过在普通 64 位计算机上在此代码中输入不同的数字来检查它：

  unsigned long long v;

  while (scanf("%llu", &v) == 1) {
    unsigned long long d;
    uint32_t r;

    d = divu64_10(v, &r);
    printf("divu10: %llu %u (C: %llu %llu)\n",
       d, r,
       v / 10, v % 10);
  }

看来我的改变正在奏效。

事实上，问题是 - 真正精通二进制算术的人能否确认它divu64_10()是否正确工作？

c