реализуйте eq, лейтенант gt в блоке без переходов
Действительно ли возможно записать логику с помощью только И, ИЛИ, и операторы NOT, чтобы сравнить 2 операнда и возвратить true (-1, 0) без использования переходов? Если так, можете Вы давать мне некоторые подсказки, поскольку это выглядит невозможным мне. Я пытаюсь реализовать eq, лейтенанта и gt в ассемблере книги "Элементы Вычислительных систем".
6 ответов
Получение результата -1 или 0 (или 1 или 0, иначе в этом отношении) из ваших операций сравнения невозможно, если вы используете только побитовые логические операторы, и добавьте / вычесть, где утерян нести:
Для битовых операторов бит N результата зависит только от бита n двух операндов.
Для дополнения рассмотрим, как работает двоичные добавления: бит N результата может влиять бит N , а биты справа от бита N (через ногой), каждого из операндов; Но нельзя влиять любые биты слева от бита N в операндах. (Вы могли бы рассмотреть это обобщение наблюдения, которые добавляют два даже номера, не могут дать нечетным результатом.)
Как одно дополнение или битовое op не может распространять какую-либо информацию слева от бита n от операндов на бит n результата, ни один состав дополнений или побитовых операций; И вычитание (при условии 2 комплемента 2) можно рассматривать как такую композицию: x-y = x + (не y) +1.
Итак, вы не можете получить результат 0 для 2 == 2, но -1 (или 1) для 2 == 4, например: бит 0 нужного результата отличается в каждом случае, но результат Может зависеть только от бита 0 двух операндов, которые одинаковы в каждом случае.
Если ваши истинные и ложные значения отличаются только в верхней части (т.е. левый), он может быть сделан .
Например, с 8-битными значениями: используйте 0x80 для true и 0 для false; Затем x == y может быть реализован как (не ((x - Y) или (y - x))) и 0x80 .
Проблема, изначально заявленная, может быть решена, могут быть решены, если доступные операции расширены, чтобы включить правильный сдвиг, или если операция добавления может производить перенос, которая может быть добавлена в нижнюю часть результата.
Это действительно одинаково отображается с функциональных языков. Причина, по которой он назван , выберите , это то, что он предназначен для использования в качестве части Linq, который использует ключевые слова SQL.
from item in collection
where item.Value == someValue
select item.Name
переводится на:
collection.Where(item => item.Value == someValue)
.Select(item => item.Name)
Было бы немного несовместим, если выбрано карта ; Что-то вроде:
collection.Filter(item => item.Value == someValue)
.Map(item => item.Name)
на самом деле, многие люди используют LINQ, не слышав о функциональном программировании вообще. Для них LINQ является методом для получения объектов данных и запросить их легко (например, запросы SQL). К ним выберите и , где имеет смысл. Намного больше чем карта и фильтр .
XOR a, b
приведет к 0, если A и B равны, и что-то ненулевое.
SUB a, b
AND a, SIGN_BIT
(где Sign_Bit - это маска для удаления всего, кроме ... подписанный бит)
приведет к нулю, если A больше B, и ненулевой, если A меньше или равно B (при условии, что 2-х годов) Отказ
На всякий случай, если это чистый теоретический вопрос: поскольку вы работаете на конечном наборе операндов, все возможные функции могут быть выражены только с использованием только или, а не.
См. дизъюнктивная нормальная форма для дальнейшего объяснения.
Для практических целей Anons Alse более полезен :-) ...
Редактировать : Даже мой теоретический ответ может быть не правдой: применение дизъюнктивного нормальной формы к этой проблеме потребует сдвиговых операций, поскольку каждый Один бит выходного слова зависит от всех битов входных битов. Я еще не выяснил, как реализовать сдвиги, используя и, или, а не и арифметики (и я не уверен, что это возможно вообще ...)
Я оставляю пост, хотя и негативный пример преждевременного ответа ..
Все арифметические операции на языке ассамблеи, о которых вы говорите о том, чтобы пойти с возможностью условных прыжков на основе Результат операции (= 0? и> 0?), которая может быть использована для получения желаемого булевого результата.
Равное B может быть выражено через xor:
(A AND (NOT B)) OR ( A AND (NOT B))
Будет выведено 0, если A == B, и что-то! = 0, если это не так
Для A меньше B вы можете использовать (A - B AND SIGN_MASK)
, где SIGN_MASK маскирует все, кроме знакового бита, даст вам истинное значение MAX_NEGATIVE_INTEGER и ложное значение 0.
Больше, чем может быть тривиально построено из меньшего, чем
]