Умножение двух целых чисел, заданных в двоичном
Я работаю над программой, которая позволит мне умножать / делить / добавлять / вычитать двоичные числа вместе. В моей программе я делаю все целые числа представленными как векторы цифр.
Мне удалось выяснить, как сделать это с помощью сложения, однако умножение заставило меня задуматься, и мне было интересно, кто-нибудь может дать мне несколько советов о том, как получить псевдокод в качестве руководства для этой программы.
Заранее спасибо!
РЕДАКТИРОВАТЬ: я пытаюсь выяснить, как создать алгоритм для умножения еще, чтобы прояснить ситуацию. Любая помощь о том, как понять этот алгоритм будет принята с благодарностью. Я обычно не работаю с C ++, поэтому мне нужно немного времени, чтобы разобраться с этим.
Решение
Вы также можете рассмотреть алгоритм Бута, если хотите умножить:
Алгоритм умножения Бута
Другие решения
Длительное умножение в псевдокоде будет выглядеть примерно так:
vector<digit> x;
vector<digit> y;
total = 0;
multiplier = 1;
for i = x->last -> x->first //start off with the least significant digit of x
total = total + i * y * multiplier
multiplier *= 10;
return total
Вы могли бы попытаться симулировать двоичный множитель или любая другая схема, которая используется в CPU.
Просто попробовал что-то, и это сработало бы, если бы вы только умножали значения без знака в двоичном виде:
unsigned int multiply(unsigned int left, unsigned int right)
{
unsigned long long result = 0; //64 bit result
unsigned int R = right; //32 bit right input
unsigned int M = left; //32 bit left input
while (R > 0)
{
if (R & 1)
{// if Least significant bit exists
result += M; //add by shifted left
}
R >>= 1;
M <<= 1; //next bit
}
/*-- if you want to check for multiplication overflow: --
if ((result >> 32) != 0)
{//if has more than 32 bits
return -1; //multiplication overflow
}*/
return (unsigned int)result;
}
Тем не менее, это на двоичном уровне … Просто у вас есть вектор цифр в качестве ввода