Возможный дубликат:
Как сложить два числа без использования ++, + или другого арифметического оператора.
Можно ли написать программу (на языке C), которая умножает два числа без использования каких-либо арифметических операторов (*, +, -, /,%).
Возможный дубликат:
Как сложить два числа без использования ++, + или другого арифметического оператора.
Можно ли написать программу (на языке C), которая умножает два числа без использования каких-либо арифметических операторов (*, +, -, /,%).
Нижеприведенный фрагмент кода может помочь, если вы согласны с побитовым оператором для добавления.
int xor, and, temp;
and = x & y;
xor = x ^ y;
while(and != 0 )
{
and <<= 1;
temp = xor ^ and;
and &= xor;
xor = temp;
}
Для умножения a и b сложите "a" "b" раз
unsigned int mult(unsigned int a,unsigned int b)
{
unsigned int counter=0;
unsigned int mult = a;
if(a == 0 || b == 0)
{
return 0;
}
//Optimize if any of the number is power of two then
//Just right shift other with value of this number
while(counter < b )
{
counter = add(counter,1);
mult = add(mult,a);
}
return mult;
}
Конечно - если машина Тьюринга может это сделать, то сможет и C (если у вас достаточно памяти). Но вы, вероятно, не увидите, как я это пишу.
Если вы хотите сделать это самостоятельно, один из способов - смоделировать умножение двух чисел на бумаге. Вы работаете с цифрами символически. Вам просто нужно разобраться с каждой цифрой и таблицей результатов для умножения этих цифр.
Для сложения двух чисел можно использовать аналогичную таблицу «сложения».
Не имеет значения, являются ли цифры, с которыми вы работаете, десятичными или двоичными - принцип тот же.
Вот как это сделать с помощью алгоритма Крестьянина. add()
из ответа, который Нира дала до меня:
#include <stdio.h>
unsigned int add(unsigned int x, unsigned int y)
{
unsigned int xor, and, temp;
and = x & y;
xor = x ^ y;
while(and != 0 ) {
and <<= 1;
temp = xor ^ and;
and &= xor;
xor = temp;
}
return xor;
}
int main()
{
unsigned int multiplicand = 41,
multiplier = 6,
res = 0;
while(multiplier != 0) {
if (multiplier & 1) {
res = add(res, multiplicand);
}
multiplier >>= 1;
multiplicand <<= 1;
}
printf("6 times 41 equals %u\n", res);
return 0;
}
Вы можете умножить два числа с помощью машины Тьюринга, которая, возможно, не использует никаких арифметических операторов, просто переместите ленту влево / вправо, добавьте / удалите отметку с ленты. Поэтому вы можете написать программу на языке C, имитирующую множитель Тьюринга.