Добавьте два числа без использования операторов + и -

Question

Предположим, у вас есть два числа, оба целые числа со знаком, и вы хотите их суммировать, но не можете использовать обычные операторы + и - вашего языка.Как бы вы это сделали?

На основе http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml

Answer 1

В Common Lisp:

(defun esoteric-sum (a b)
  (let ((and (logand a b)))
    (if (zerop and)
        ;; No carrying necessary.
        (logior a b)
        ;; Combine the partial sum with the carried bits again.
        (esoteric-sum (logxor a b) (ash and 1)))))

Это принимает битов и чисел, которые определяют, какие биты должны быть перенесены, и, если нет битов, требующих сдвига, возвращает битов или операндов. В противном случае он сдвигает перенесенные биты на один влево и объединяет их снова с побитовым-исключительным-или чисел, который суммирует все биты, которые не нужно переносить, до тех пор, пока не прекратится перенос. необходимо.

Вот итерационная альтернатива рекурсивной форме выше:

(defun esoteric-sum-iterative (a b)
  (loop for first = a then (logxor first second)
        for second = b then (ash and 1)
        for and = (logand first second)
        until (zerop and)
        finally (return (logior first second))))

Обратите внимание, что функция нуждается в другой уступке, чтобы преодолеть Нежелание Common Lisp использовать арифметику дополнения с фиксированной шириной два - обычно неизмеримый актив & mdash; но я бы не стал омрачать форму функции этим случайным сложность.

Если вам нужно больше подробностей о , почему работает, пожалуйста, задайте более подробный вопрос, чтобы исследовать тему.

Answer 2

Эта версия имеет ограничение на диапазон номеров:

(((int64_t)a << 32) | ((int64_t)b & INT64_C(0xFFFFFFFF)) % 0xFFFFFFFF

Это также относится к категории "буквы правил".

Answer 3

Если мы подчиняемся букве правил:

a += b;

В противном случае http://www.geekinterview.com/question_details/67647 имеет довольно полный список.