Задача о сложении

Условие

В IT-отдел принесли странную «коробку» от дочернего исследовательского центра — компактный аппаратный ускоритель для обработки сигналов. На борту стоял быстрый, процессор, но конструкторы сознательно упростили его набор команд ради энергоэффективности, поэтому у чипа осталась только операция суммирования. Другие арифметические операции либо не были реализованы в железе, либо временно отключены.

Задача

Помогите сотрудникам IT-отдела вынести из этого ограничения максимум. Реализуйте  вычитание, умножение и деление, но только с помощью операции суммирования. Язык программирования неважен, ограничений по мощности компьютера также нет.

Решение

Все примеры приведены на псевдокоде.

Вычитание

Начнем с вычитания. Операцию a – b можно заменить на a + (-b). То есть наша задача — написать функцию, которая бы возвращала отрицательное значение для числа. Для этого придется вспомнить двоичную арифметику — дополнительный код числа, который используется для представления отрицательных чисел.

Чтобы его получить, нужно:

1. Представить b в виде двоичного числа.
2. Инвертировать все биты.
3. К инвертированному результату прибавить 1.

Например, для цифры «5» порядок действий будет такой:

1. В двоичной системе пять — это 0х00000101.
2. Инвертируем биты: 0х11111010.
3. Прибавим один бит: 0х11111011.

Теперь попробуем найти какое-нибудь значение, например 7 – 5. Дополнительный код от пяти знаем, осталось перевести семь в двоичную систему и сложить два числа:

1. Семь в двоичной — 0х00000111.
2. 0х00000111 + 0х11111011 = 0х00000010.

Получаем 0х00000010 или 2 в десятичной системе.

Осталось написать это на псевдокоде:

      bitset<8> a(7); //число a в двоичной записи
bitset<8> b(5); //число b в двоичной записи
bitset<8> result; //результат
bitset<8> b_inv(5) = ~b; //инвертируем значение, здесь «~» — оператор побитового отрицания в C++
b_inv = b_inv + 0x00000001; //прибавляем один бит
result = a + b_inv;

Умножение

Для умножения все проще: a * b означает a + a + a… b раз, то есть для реализации достаточно цикла.

Псевдокод:

      int a = 7;
int b = 5;
int sum = 0;

for (i = 1; i <= abs(b); i++)
{ 
	sum += a; //суммируем пять раз переменную а
}
if ((b < 0) || (a < 0) && not((a < 0) && (b < 0)))
	return negative(sum); //если один из множителей отрицательный, возвращаем отрицательный результат
else
	return sum;

negative — функция, которая возвращает отрицательное значение для числа. Ее можно реализовать так же, как и в предыдущем блоке:

      negative(int number)
{
	bitset<8> a(number); //получаем набор бит от числа
	a = ~a; //инвертируем биты
	a = a + 0x00000001; //прибавляем один бит
	return a.to_ulong(); //возвращаем приведенный к int результат
}

abs — функция, которая возвращает абсолютное значение без знака. Реализовать ее можно так:

      abs(a)
{
	if(a > 0) return a;
	else return negative(a);
}

Деление

Деление a/b можно представить в виде цикла: пока (sum < a), sum += b;

Другими словами, деление — это количество операций суммирования b, пока мы не получим a. Реализовать можно так:

      int a;
int b;
if (b == 0)
return exception; //проверяем, не равен ли делитель нулю
sum = 0;
result = 0;
while (sum < a)
{
	sum += b;
	result++; //считаем количество операций суммирования
}

if(((a < 0) || (b < 0)) && not((a < 0) && (b < 0)))
	return negative(result); //проверяем, являются ли делимое или делитель отрицательными
else
	return result;
get_reminder(a, sum); //получаем остаток от деления

Функция get_reminder возвращает остаток от деления. Для этого нужно вычесть из делимого — переменной a — результат суммирования — переменную sum. Вот как это можно сделать:

      get_reminder(dividend, sum)
bitset<8> a(dividend); //делитель в двоичной записи
bitset<8> b(sum); //переменная sum в двоичной записи
bitset<8> remainder; //остаток от деления
bitset<8> sum_inv(5) = ~sum; //инвертируем значение, здесь «~» — оператор побитового отрицания в C++
sum_inv = sum_inv.to_ulong() + 1; //прибавляем один бит
remainder = a + sum_inv;
return remainder;