主页 / 问题 / 671733
Accepted
avp
Asked:2020-05-28 05:05:26 +0800 CST2020-05-28 05:05:26 +0800 CST

余数 uint64_t 除以 10

  • 772

在 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

2 个回答

  1. Best Answer

    让我们看看源代码是如何工作的。

    它计算q = n * 0x33333333 >> 33，这大约等于n * 0.0999999999...。
    然后计算误差n - q*10，如果小于 10，则一切正确，
    如果大于 10，则将结果加 1。

    让我们看看错误值。

    10 * 0x33333333 / 2 ** 33 = 0b00.111111111111111111111111111111110
11 * 0x33333333 / 2 ** 33 = 0b01.000110011001100110011001100110001
19 * 0x33333333 / 2 ** 33 = 0b01.111001100110011001100110011001001
20 * 0x33333333 / 2 ** 33 = 0b01.111111111111111111111111111111100
21 * 0x33333333 / 2 ** 33 = 0b10.000110011001100110011001100101111
...
65530 * 0x33333333 / 2 ** 33 = 6552.999998474261 =
                 0b1100110011000.111111111111111111100110011001110
...
4294967290 * 0x33333333 / 2 ** 33 = 429496728.9 =
 0b11001100110011001100110011000.111001100110011001100110011001110

    可以看出，对于n = 10*d + r，如果 r=0，则误差为 10。

    可以计算出，如果不是移位而是除法，那么误差将等于

    n - n * 10 * 0x33333333 / 2**33 = n / 2 ** 32

    由于n < 2 ** 32，结果的误差不超过 1。

    对于 64 位，一切都一样，只是我们考虑n * 0x3333333333333333 >> 65。

    添加q += q >> 32相当于乘以(2**32+1)/2**32, 而(2**32+1)*0x33333333 = 0x3333333333333333.

    • 5

  2. 从 GCC 为 ARM 10_3 调用 __aeabi_uldivmod 函数的标准除法 - 在 DWT 计数器的 269 个滴答中执行。大胆的。通过乘以小数除以 10 比移位快 18%。通过在函数中保存上下文引入了显着的延迟——操作需要太多的寄存器。

    乘法除法需要 67 个时钟周期，需要 Cortex-M3/M4 或更高版本。

    union divrev
{
    uint64_t w64;
    uint32_t w32[2];
};

__attribute__ ((optimize("-Og")))
uint64_t divu64_10(uint32_t* residue, uint64_t value)//72
{
    uint32_t res, t10, magh, magl;
    union divrev rev;
    union divrev rew;
    rev.w64 = value;
    magh = 3435973837UL; magl = 429496730UL; t10 = 10;
    rew.w32[1] = ((uint64_t)rev.w32[1] * magh >> 35);
    rew.w32[0] = 0;
    rev.w64 = (uint64_t)rev.w64 - rew.w64 * t10;
    res = ((uint64_t)rev.w64 >> 16);
    res = ((uint64_t)res * magl >> 32);
    rew.w32[0] = res << 16;
    rev.w64 = (uint64_t)rev.w64 - rew.w32[0] * t10;
    res = ((uint64_t)rev.w32[0] * magl >> 32);
    rew.w32[0] += res;
    res = rev.w32[0] - res * t10;
    *residue = res;
    return rew.w64;
};

    如果该函数生成一个完成的字符串，您可以将速度提高 13 倍。char* tail_txt 是数组的尾部，最小大小为 24 字节。

    char* u64_char (char* tail_txt, uint64_t value)//100
{
    uint32_t res, t10, magh, magl;
    union divrev rev;
    union divrev rew;
    rev.w64 = value;
    *tail_txt = 0;
    magh = 3435973837UL; t10 = 10; magl = 429496730UL;
    do{
        rew.w32[1] = ((uint64_t)rev.w32[1] * magh >> 35);
        rew.w32[0] = 0;
        rev.w64 = (uint64_t)rev.w64 - rew.w64 * t10;
        res = ((uint64_t)rev.w64 >> 16);
        res = ((uint64_t)res * magl >> 32);
        rew.w32[0] = res << 16;
        rev.w64 = (uint64_t)rev.w64 - rew.w32[0] * t10;
        res = ((uint64_t)rev.w32[0] * magl >> 32);
        rew.w32[0] += res;
        rev.w32[0] += '0';
        res = (rev.w32[0] - res * t10);
        *(--tail_txt) = res;
        rev.w64 = (uint64_t)rew.w64;
    }while (rev.w32[1]);
    if (rev.w32[0] == 0) return tail_txt;
    do{
        rev.w32[1] = ((uint64_t)rev.w32[0] * magh >> 32);
        res = rev.w32[0] + '0';
        rev.w32[0] = rev.w32[1] >> 3;
        res -=  rev.w32[0] * t10;
        *(--tail_txt) = res;
    }while (rev.w32[0]);
    return tail_txt;
};
    • 2

相关问题