Как найти меньшее из двух двоичных чисел с в основном только побитовой логикой?

Question

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

Мне нужно это для задания, чтобы выразить некоторые фрагменты Си на очень минимальном языке ассемблера.

Единственное, что я придумал, это различие между 3 случаями:

1. Если одно число отрицательное, а другое положительное, у нас есть решение.

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

3. Если оба отрицательны, сделайте их положительными, то есть возьмите два дополнения обоих и перейдите к шагу 2.

Но это кажется довольно обширным для "простого" условия.

Может быть, я просто глуп и не вижу очевидного решения:)

Answer 1

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

loop
  Set A to one closer to zero
  Set B one closer to zero
until either A is 0 or B is zero

Когда вы получаете либо A, либо B на ноль, то этот - меньше. Обратите внимание, что это работает для двух негативов или двух позитивов. Итак, теперь у вас есть известное решение; удобно, у вас есть инструкция добавления, поэтому вам не нужно это реализовывать.

Но это О (н). Что вы можете сделать лучше? (Подсказка: вы должны быть в состоянии получить O(LG N).)

Рассмотрим, что такое сдвиг вправо в двоичном числе: по сути, это деление на 2.

Посмотрите, поможет ли этот намек.

Вот альтернативная мысль: если у вас есть сложение по ширине слова, как вы можете превратить сложение в вычитание? Если вы можете сделать это. Вы можете вычесть А из В и посмотреть, как получается разница.