Вычислять показатели степени только сложением

Почему бы и нет для небольших целых чисел?

Во-первых, реализуйте умножение с использованием повторного сложения. Затем реализуйте pow(), используя многократное умножение. Будет медленно, но работать будет нормально.

Существует более быстрый алгоритм возведения в степень, который называется возведение в степень возведением в степень. Однако, учитывая, что у вас нет быстрого умножения, я не уверен, что оно того стоит - вы можете сначала поработать над реализацией алгоритма быстрого умножения.

В соответствии с ответом 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;
}

Подобно решению 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;
}

Это очень реалистично. Еще не так много лет назад у процессоров не было АЛУ, которое могло бы выполнять какие-либо сложные операции, такие как умножение и деление.

Умножение обычно выполняется с помощью сдвига и сложения. Вот псевдосборка:

; 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)

Вы можете найти статью в Википедии об умножении ALU. С помощью сложения и побитовых операций (и и или) вы можете реализовать умножение за один шаг на бит, вместо того, чтобы складывать столько раз, сколько раз меньше значение меньшего оператора.

показатель n в степени k:

exponent(n,k) {
   for(x=1..n)
      x = x + exponent(x,k-1)
}