RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 671733
Accepted
avp
avp
Asked:2020-05-28 05:05:26 +0000 UTC2020-05-28 05:05:26 +0000 UTC 2020-05-28 05:05:26 +0000 UTC

余数 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 2 个回答
  • 10 Views

2 个回答

  • Voted
  1. Best Answer
    Abyx
    2020-06-03T05:01:36Z2020-06-03T05:01:36Z

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

    它计算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. AVI-crak Home
    2022-04-09T06:15:27Z2022-04-09T06:15:27Z

    从 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

相关问题

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    Python 3.6 - 安装 MySQL (Windows)

    • 1 个回答
  • Marko Smith

    C++ 编写程序“计算单个岛屿”。填充一个二维数组 12x12 0 和 1

    • 2 个回答
  • Marko Smith

    返回指针的函数

    • 1 个回答
  • Marko Smith

    我使用 django 管理面板添加图像,但它没有显示

    • 1 个回答
  • Marko Smith

    这些条目是什么意思,它们的完整等效项是什么样的

    • 2 个回答
  • Marko Smith

    浏览器仍然缓存文件数据

    • 1 个回答
  • Marko Smith

    在 Excel VBA 中激活工作表的问题

    • 3 个回答
  • Marko Smith

    为什么内置类型中包含复数而小数不包含?

    • 2 个回答
  • Marko Smith

    获得唯一途径

    • 3 个回答
  • Marko Smith

    告诉我一个像幻灯片一样创建滚动的库

    • 1 个回答
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Алексей Шиманский 如何以及通过什么方式来查找 Javascript 代码中的错误? 2020-08-03 00:21:37 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    user207618 Codegolf——组合选择算法的实现 2020-10-23 18:46:29 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5