53

是否可以通过使用纯位移、加法、减法甚至乘法将无符号整数除以10？使用资源非常有限且除法速度较慢的处理器。

4

9 回答 9

65

编者注：这实际上不是编译器所做的，并且对于以 9 结尾的大正整数给出了错误的答案div10(1073741829) = 107374183，而不是从 107374182 开始。不过，对于较小的输入来说，这对于某些用途来说可能已经足够了。

编译器（包括 MSVC）确实对常数除数使用定点乘法逆运算，但它们使用不同的魔法常数并对高半结果进行移位以获得所有可能输入的精确结果，与 C 抽象机的要求相匹配。请参阅Granlund & Montgomery关于算法的论文。

请参阅为什么 GCC 在实现整数除法时使用乘以一个奇怪的数字？有关实际 x86 asm gcc、clang、MSVC、ICC 和其他现代编译器的示例。

这是一个快速的近似值，对于大输入是不精确的

它甚至比编译器使用的乘法+右移的精确除法还要快。

您可以使用乘法结果的高半部分除以小整数常数。假设一台 32 位机器（代码可以相应调整）：

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

这里发生的是我们乘以 1/10 * 2^32 的近似值，然后删除 2^32。这种方法可以适应不同的除数和不同的位宽。

这对 ia32 架构非常有效，因为它的 IMUL 指令会将 64 位乘积放入 edx:eax，而 edx 值将是想要的值。即（假设股息在 eax 中传递，商在 eax 中返回）

div10 proc 
    mov    edx,1999999Ah    ; load 1/10 * 2^32
    imul   eax              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
    endp

即使在具有慢速乘法指令的机器上，这也比软件甚至硬件除法要快。

于 2011-04-05T21:14:32.017 回答
42

尽管到目前为止给出的答案与实际问题相匹配，但它们与标题不匹配。因此，这里有一个深受Hacker's Delight启发的解决方案，它真正只使用位移位。

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 << 2) + q) << 1);
    return q + (r > 9);
}

我认为这是缺乏乘法指令的架构的最佳解决方案。

于 2013-09-29T08:56:52.213 回答
21

当然，如果您可以忍受一些精度损失，则可以。如果您知道输入值的值范围，则可以得出一个位移位和一个精确的乘法。一些示例如何除以 10、60 ......就像本博客中描述的那样，以最快的方式格式化时间。

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10
于 2011-04-05T21:12:48.740 回答
5

为了稍微扩展 Alois 的答案，我们可以将建议扩展y = (x * 205) >> 11为更多的倍数/班次：

y = (ms *        1) >>  3 // first error 8
y = (ms *        2) >>  4 // 8
y = (ms *        4) >>  5 // 8
y = (ms *        7) >>  6 // 19
y = (ms *       13) >>  7 // 69
y = (ms *       26) >>  8 // 69
y = (ms *       52) >>  9 // 69
y = (ms *      103) >> 10 // 179
y = (ms *      205) >> 11 // 1029
y = (ms *      410) >> 12 // 1029
y = (ms *      820) >> 13 // 1029
y = (ms *     1639) >> 14 // 2739
y = (ms *     3277) >> 15 // 16389
y = (ms *     6554) >> 16 // 16389
y = (ms *    13108) >> 17 // 16389
y = (ms *    26215) >> 18 // 43699
y = (ms *    52429) >> 19 // 262149
y = (ms *   104858) >> 20 // 262149
y = (ms *   209716) >> 21 // 262149
y = (ms *   419431) >> 22 // 699059
y = (ms *   838861) >> 23 // 4194309
y = (ms *  1677722) >> 24 // 4194309
y = (ms *  3355444) >> 25 // 4194309
y = (ms *  6710887) >> 26 // 11184819
y = (ms * 13421773) >> 27 // 67108869

每行都是一个独立的计算，您将在注释中显示的值处看到您的第一个“错误”/不正确结果。对于给定的错误值，您通常最好采用最小的移位，因为这将最小化在计算中存储中间值所需的额外位，例如(x * 13) >> 7“更好”，(x * 52) >> 9因为它需要更少的两位开销，而两者都开始给出68以上的错误答案。

如果您想计算更多这些，可以使用以下（Python）代码：

def mul_from_shift(shift):
    mid = 2**shift + 5.
    return int(round(mid / 10.))

我做了很明显的事情来计算这个近似值何时开始出错：

def first_err(mul, shift):
    i = 1
    while True:
        y = (i * mul) >> shift
        if y != i // 10:
            return i
        i += 1

（请注意，//它用于“整数”除法，即它向零截断/舍入）

错误中出现“3/1”模式的原因（即 8 次重复 3 次，然后是 9 次）似乎是由于碱基的变化，即log2(10)约为 3.32。如果我们绘制错误，我们会得到以下信息：

错误

其中相对误差由下式给出：mul_from_shift(shift) / (1<<shift) - 0.1

于 2019-05-20T09:15:19.527 回答
3

在一次只能移动一个位置的架构上，与 2 乘以 10 的递减幂进行一系列明确的比较可能比黑客喜欢的解决方案更有效。假设一个 16 位的红利：

uint16_t div10(uint16_t dividend) {
  uint16_t quotient = 0;
  #define div10_step(n) \
    do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0)
  div10_step(0x1000);
  div10_step(0x0800);
  div10_step(0x0400);
  div10_step(0x0200);
  div10_step(0x0100);
  div10_step(0x0080);
  div10_step(0x0040);
  div10_step(0x0020);
  div10_step(0x0010);
  div10_step(0x0008);
  div10_step(0x0004);
  div10_step(0x0002);
  div10_step(0x0001);
  #undef div10_step
  if (dividend >= 5) ++quotient; // round the result (optional)
  return quotient;
}
于 2015-12-14T19:51:28.390 回答
3

考虑到 Kuba Ober 的回应，还有另一位与此相同。它使用结果的迭代近似，但我不希望有任何令人惊讶的表现。

假设我们必须找到x哪里x = v / 10。

我们将使用逆运算v = x * 10，因为它具有良好的性质，即当x = a + b，则x * 10 = a * 10 + b * 10。

让我们x用作迄今为止保持结果的最佳近似值的变量。当搜索结束时，x将保留结果。我们将设置从最重要到最不重要的每一位，一个接一个，b结束比较。如果它小于或等于，则该位设置为。为了测试下一位，我们只需将 b 向右移动一个位置（除以二）。x(x + b) * 10vvbx

x * 10我们可以通过保持和b * 10其他变量来避免乘以 10 。

这产生了以下除以v10 的算法。

uin16_t x = 0, x10 = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    uint16_t t = x10 + b10;
    if (t <= v) {
        x10 = t;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

编辑： 要获得避免需要变量的 Kuba Ober 算法，我们可以从andx10中减去。在这种情况下不再需要。算法变成b10vv10x10

uin16_t x = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    if (b10 <= v) {
        v -= b10;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

循环可以展开，并且 和 的不同值b可以b10预先计算为常数。

于 2017-10-18T18:53:46.190 回答
2

那么除法就是减法，所以是的。右移 1（除以 2）。现在从结果中减去 5，计算减法的次数，直到值小于 5。结果是减法的次数。哦，除法可能会更快。

如果除法器中的逻辑尚未为您执行此操作，则使用正常除法将右移然后除以 5 的混合策略可能会提高性能。

于 2011-04-05T21:12:46.010 回答
0

我在 AVR 汇编中设计了一种新方法，仅使用 lsr/ror 和 sub/sbc。它除以 8，然后减去除以 64 和 128 的数字，然后减去第 1,024 和第 2,048，依此类推。工作非常可靠（包括精确舍入）和快速（1 MHz 时为 370 微秒）。16 位数字 的源代码在这里：http: //www.avr-asm-tutorial.net/avr_en/beginner/DIV10/div10_16rd.asm 评论此源代码的页面在这里： http://www .avr-asm-tutorial.net/avr_en/beginner/DIV10/DIV10.html 我希望它有所帮助，即使这个问题已经存在十年了。brgs, gsc

于 2021-06-20T06:54:32.127 回答
-1

elemakil 的评论代码可以在这里找到：https ://doc.lagout.org/security/Hackers%20Delight.pdf 第 233 页。“无符号除以 10 [和 11。]”

于 2020-06-12T23:02:07.010 回答