Напишите функцию суммирования двух целых чисел без использования «+» и других арифметических операторов

Первое, что приходит в голову, — обработка битов. Почему? У нас нет выбора — нельзя использовать оператор «+». Так что будем суммировать числа так, как это делают компьютеры!

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

Так что давайте рассмотрим дополнительную задачу. Мы будем использовать десятичную систему счисления.

Чтобы просуммировать 759 + 674, я обычно складываю digit[0] обоих чисел, переношу единицу, затем перехожу к digit[1], переношу и т.д. Точно так же можно работать с битами: просуммировать все разряды и при необходимости сделать переносы единиц.

Можно ли упростить алгоритм? Да! Допустим, я хочу разделить «суммирование» и «перенос». Мне придется проделать следующее:

1. Выполнить операцию 759 + 674, забыв о переносе. В результате получится 323.
2. Выполнить операцию 759 + 674, но сделать только переносы (без суммирования разрядов). В результате получится 1110.
3. Теперь нужно сложить результаты первых двух операций (используя тот же механизм, описанный в шагах 1 и 2): 1110 + 323 = 1433.

Теперь вернемся к двоичной системе.

1. Если просуммировать пару двоичных чисел, без учета переноса знака, то i-й просуммированный бит может быть нулевым, только если i-e биты чисел a и b совпадали (оба имели значение 0 или 1). Это классическая операция XOR.
2. Если суммировать пару чисел, выполняя только перенос, то i-му биту суммы присваивается значение 1, только если i-1-е биты обоих чисел (a и b) имели значение 1. Это операция AND со смещением.
3. Нужно повторять эти шаги до тех пор, пока не останется переносов.

Следующий код реализует данный алгоритм.

			public static int add(int a, int b)	{
	if (b == 0) return a;
	int sum = a ^ b;			// добавляем без переноса
	int carry = (a & b) << 1;	// перенос без суммирования
	return add(sum, carry);		// рекурсия
}
		

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

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).