C-从零开始

Question

我编写了这段代码，不用使用C的内置操作符就可以完成除法：

#include <stdio.h>
#include <math.h>

int idiv(int a, int b) {
    return a * (pow(b, -1));
}

int main(void) {
    /* 15/3 is 5 */
    printf("%d\n", idiv(15, 3));
    return 0;
}

我能做些什么让代码更快吗？我用除法操作符对它进行了基准测试，它的速度超过了10倍。

Answer 1

目前还不清楚您使用的是什么工具链，以及目标处理器是什么。但是，我可以猜到性能下降。pow函数通常适用于浮点值。而且，最有可能的权力与负优势也将使用除法。我用ARM gcc 8.2用-O3标志编译了以下代码：

#include <math.h>

int idiv(int a, int b) {
    return a * (pow(b, -1));
}

int idiv2(int a, int b) {

    return a/b;
}

我的名单如下：

idiv:
        push    {r4, r5, r6, lr}
        mov     r6, r0
        mov     r0, r1
        bl      __aeabi_i2d
        mov     r2, r0
        mov     r3, r1
        mov     r0, #0
        ldr     r1, .L4
        bl      __aeabi_ddiv
        mov     r4, r0
        mov     r0, r6
        mov     r5, r1
        bl      __aeabi_i2d
        mov     r2, r0
        mov     r3, r1
        mov     r0, r4
        mov     r1, r5
        bl      __aeabi_dmul
        bl      __aeabi_d2iz
        pop     {r4, r5, r6, pc}
.L4:
        .word   1072693248
idiv2:
        push    {r4, lr}
        bl      __aeabi_idiv
        pop     {r4, pc}

从assebly代码来看，性能问题的解决是显而易见的。我们仍然依赖ABI。如果您想拥有只使用assebly指令的代码？然后可以用“移位和减法”实现整数除法。或者你可以在谷歌上搜索它的一些开源实现。例如，我找到了一个这里。下面是来自这里的稍微修改的示例：

void unsigned_divide(unsigned int dividend,
             unsigned int divisor,
             unsigned int *quotient,
             unsigned int *remainder )
{
  unsigned int t, num_bits;
  unsigned int q, bit, d;
  int i;

  *remainder = 0;
  *quotient = 0;

  if (divisor == 0)
    return;

  if (divisor > dividend) {
    *remainder = dividend;
    return;
  }

  if (divisor == dividend) {
    *quotient = 1;
    return;
  }

  num_bits = 32;

  while (*remainder < divisor) {
    bit = (dividend & 0x80000000) >> 31;
    *remainder = (*remainder << 1) | bit;
    d = dividend;
    dividend = dividend << 1;
    num_bits--;
  }

  /* The loop, above, always goes one iteration too far.
     To avoid inserting an "if" statement inside the loop
     the last iteration is simply reversed. */
  dividend = d;
  *remainder = *remainder >> 1;
  num_bits++;

  for (i = 0; i < num_bits; i++) {
    bit = (dividend & 0x80000000) >> 31;
    *remainder = (*remainder << 1) | bit;
    t = *remainder - divisor;
    q = !((t & 0x80000000) >> 31);
    dividend = dividend << 1;
    *quotient = (*quotient << 1) | q;
    if (q) {
       *remainder = t;
     }
  }
}  /* unsigned_divide */

#define ABS(x)  ((x) < 0 ? -(x) : (x))

void signed_divide(int dividend,
           int divisor,
           int *quotient,
           int *remainder )
{
  unsigned int dend, dor;
  unsigned int q, r;

  dend = ABS(dividend);
  dor  = ABS(divisor);
  unsigned_divide( dend, dor, &q, &r );

  /* the sign of the remainder is the same as the sign of the dividend
     and the quotient is negated if the signs of the operands are
     opposite */
  *quotient = q;
  if (dividend < 0) {
    *remainder = -r;
    if (divisor > 0)
      *quotient = -q;
  }
  else { /* positive dividend */
    *remainder = r;
    if (divisor < 0)
      *quotient = -q;
  }

} /* signed_divide */

您可以采取任何，核实，并优化它根据您的需要。广义函数通常比专门函数更复杂。