2

我们正在编写一个非常简单的程序来在我们为一个类构建的处理器上执行。它没有乘法或除法的能力。但是，我们确实支持循环控制的加法、减法、和、或和分支（如果您熟悉 MIPS，则如相等的分支）。我们在想一个可以在上面运行的简洁程序应该是某种 x^n 程序。当然，这些数字必须进行硬编码，但考虑到我们处理器的限制，这是否现实？

是否有仅计算指数的加法？谢谢。

4

6 回答 6

7

对于小整数，为什么不呢？

首先，使用重复加法实现乘法。然后，使用重复乘法实现 pow() 。它会很慢，但它会正常工作。

有一种更快的求幂算法，称为Exponentiation by Squaring。但是，鉴于您没有快速乘法，我不确定它是否值得 - 您可能希望首先实现快速乘法算法。

于 2009-12-13T23:35:11.593 回答
6

符合 dmazzoni 在 c 样式语法中的响应：

int mulitply(int x, int y)
{
    int product;

    for (int i = 0; i<y; i++)
       product += x;

    return product;
}

int power(int x, int exponent)
{
    int result = 1;

    for (int i = 0; i < exponent; i++)
        result = multiply(result, x);

    return result;
}
于 2009-12-13T23:40:31.300 回答
2

与 Aequitarum 的解决方案类似，但对幂使用重复平方，对乘法使用重复加倍。对于大 x,y 应该更快：

int multiply(int x, int y) {
  int product = 0;
  int bitmask = 1;

  while (y >= bitmask) {
    if (y & bitmask) product += x;
    x += x;
    bitmask += bitmask;
  }
  return product;
}

int power(int x, int exponent)
{
  int result = 1;
  int bitmask = 1;

  while (exponent >= bitmask) {
    if (exponent & bitmask) result = multiply(result, x);
    x = multiply(x, x);
    bitmask += bitmask;
  }
  return result;
}
于 2009-12-14T07:52:32.650 回答
0

指数 n 的 k 次幂：

exponent(n,k) {
   for(x=1..n)
      x = x + exponent(x,k-1)
}
于 2009-12-19T21:09:46.507 回答
0

您可能会发现有关乘法 ALU的 Wikipedia 文章。使用加法和按位运算（and 和 or），您可以一步一步地实现乘法运算，而不必像较小运算符的大小一样多次相加。

于 2009-12-14T09:54:25.430 回答
0

这是非常现实的。几年前，处理器还没有可以执行任何高级运算（如乘法和除法）的 ALU。

乘法通常使用移位和加法来完成。这是一些伪汇编：

; multiply registers a and b

; use c as high b
mov c,#0
; use d as low result
mov d,#0
; use e as high result
mov e,#0
.nextbit:
  ; shift low bit out of a
  shr a
  ; skip if zero
  bcc .noadd
    ; add b to result
    add d,b
    adc e,c
  .noadd:
  ; double b
  shl b
  rcl c
  ; test a
  cmp a,#0
bne .nextbit

（请注意，两个字节值相乘的结果是一个两个字节值。）

一旦你有了乘法，你就可以循环计算功率。

使用说明：

mov x,y = move y into x
shr x = shift right one bit
shl x = shift left one bit
rcl x = rotate left one bit with carry inserted
add x,y = add y to x
adc x,y = add y to x with carry
cmp x,y = compare x to y
bcc = branch on carry clear
bne = branch on not equal
#0 = literal number zero (as opposed to 0, which would be the address zero)
于 2009-12-14T00:05:54.067 回答