алгоритм имитации умножения путем сложения

какой-то псевдокод:

function multiply(x, y)
  if abs(x) = x and abs(y) = y or abs(x) <> x and abs(y) <> y then sign = 'plus'
  if abs(x) = x and abs(y) <> y or abs(x) <> x and abs(y) = y then sign = 'minus'

 res = 0
 for i = 0 to abs(y)
  res = res + abs(x)
 end

 if sign = 'plus' return res
    else return -1 * res

end function

Как насчет этого для целых чисел:

int multiply(int a, int b)
{
    int product = 0;
    int i;
    if ( b > 0 )
    {
        for(i = 0; i < b ; i++)
        {
            product += a;
        }
    }
    else
    {
        for(i = 0; i > b ; i--)
        {
            product -= a;
        }
    }

    return product;
}

Я попал сюда, потому что искал алгоритм умножения без использования операции *. Все, что я вижу здесь, это просто добавление или вычитание числа n раз. Это O(n), и это нормально, но...

Если у вас есть bitwise shift операций, вы можете получить алгоритм O(log n) для умножения.

Вот мой псевдокод:

function mul(n, x)
    if n < 0 then   # 'n' cannot be negative
        n := -n
        x := -x
    endif

    y := 0
    while n != 0 do
        if n % 2 == 0 then
            x := x << 1     # x := x + x
            n := n >> 1     # n := n / 2
        else
            y := y + x
            x := x << 1     # x := x + x
            n := n - 1      # n := (n-1)/2
            n := n >> 1
        endif
    endwhile

    return y                # y = n * x
end

Помните, что функция выше для mul(1000000, 2) — это O(log 1000000), а для mul(2, 1000000) — только O(log 2).

Конечно, вы получите те же результаты, но имейте в виду, что порядок параметров в вызове функции имеет значение.

Изменить: боковое примечание для использования n % 2

Реализация n % 2 с использованием bitwise shift

Это довольно просто. Сначала разделите n на 2, затем умножьте n на 2 и проверьте, изменилось ли n. Псевдокод:

function is_even(n)
    n_original := n
    n := n >> 1        # n := n / 2
    n := n << 1        # n := n * 2
    if n = n_original then
        return true    # n is even
    else
        return false   # n is not even
    endif
end

Реализация n % 2 с использованием bitwise and

function is_even(n)
    if n and 1 = 0 then
        return true
    else
        return false
    endif
end