Как я могу определить, произошло ли переполнение с помощью AND OR NOT и XOR?

Я пытаюсь использовать только AND OR XOR и NOT, чтобы определить, будет ли переполнение при добавлении 2 двоичных чисел, состоящих из 4 бит. Я знаю, например, что что-то вроде 1100 + 0100 завершится как 1 | 0000. Но как я могу найти это, используя только эти логические операторы?

Я пытаюсь получить 1000, когда происходит переполнение, и 0000, когда этого не происходит. Это достаточно просто, так как я могу просто использовать XOR с маской, чтобы очистить последние 3 бита.

У кого-нибудь есть предложения, как это выяснить?


logical-operators overflow bits
person John    schedule 26.01.2011    source источник
comment
Это полностью зависит от языка, с чем вы работаете?   -  person Michael Berry    schedule 26.01.2011
comment
Я пока пытаюсь сделать это на бумаге. Я полагаю, как только я на самом деле выясню, как это сделать, тогда я буду двигаться дальше.   -  person John    schedule 26.01.2011
comment
Пока я просто пытаюсь выяснить (на бумаге), как использовать операторы для обнаружения переполнения при добавлении любых двух двоичных чисел.   -  person John    schedule 26.01.2011
comment
Как это может зависеть от языка, если в нем используются только логические операторы... Я думаю, Джон, на этот вопрос будет дан ответ, если я его получу.   -  person kaoD    schedule 26.01.2011
comment
Лучшее, что я мог придумать, это что-то вроде использования маски 1111 и XOR, чтобы сделать 1-е число отрицательным, а затем использовать XOR, чтобы добавить это к 1-му числу и снова добавить его ко 2-му числу, а затем используя И, чтобы сравнить результат с исходным вторым числом. Если произошло переполнение, то результирующие биты будут отличаться от начальных битов. (К сожалению, это не работает, поэтому я что-то делаю не так, но не вижу где).   -  person John    schedule 26.01.2011

Ответы (3)


arrow_upward
1
arrow_downward

Числа — это ABCD и EFGH, ^ — это И, | является ИЛИ.

(A^E) | (B^F^(A|E)) | (C^G^(B|F)^(A|E)) | (D^H^(C|G)^(B|F)^(A|E))

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

person kaoD    schedule 26.01.2011

arrow_upward
1
arrow_downward

Я застрял на том же вопросе в течение последних нескольких дней и понял ответ. Предполагая, что есть два 4-битных числа a, b и их сумма хранится в другом 4-битном числе s, происходит переполнение, когда следуют первые биты.

a = 0, b = 0, s = 1
a = 1, b = 1, s = 0

(NOT a) AND (NOT b) AND s возвращает 1 для первого случая переполнения a AND b AND (NOT s) возвращает 1 для второго случая. Вы можете использовать ИЛИ для получения 1 в качестве первого бита результата. Так,

((NOT a) AND (NOT b) AND s) OR (a AND b AND (NOT s))

выражение возвращает 1xxx в случае переполнения. Объединение приведенного выше выражения с 1000 возвращает 1000 при наличии переполнения и 0000 при отсутствии переполнения. Итак, окончательный ответ:

(((NOT a) AND (NOT b) AND s) OR (a AND b AND (NOT s))) AND 1000

PS: я предположил, что сумма была доступна в другой переменной, которую другие ответы не предполагали

person Ray    schedule 04.06.2020
comment
Примечание: этот ответ использует s = a+b в качестве входных данных. В других ответах этого нет, и этот вопрос немного отличается от процедуры определения того, происходит ли переполнение при добавлении. Наличие этой суммы в качестве входных данных делает ее намного проще, что хорошо, и более актуально/интересно для реальных ситуаций переполнения. (Возможно, я не должен был закрывать это как дубликат; изначально я пропустил эту разницу.) Но в любом случае, хороший ответ, я думаю, что это выглядит правильно. - person Peter Cordes; 04.06.2020
comment
Хорошо, спасибо, что сообщили мне. Я добавлю PS, упомянув, что я предположил, что сумма была доступна в другой переменной. - person Ray; 04.06.2020

arrow_upward
0
arrow_downward

Я думаю, что это будет работать, не используя циклы или сдвиги. Но некрасиво:

if (
(a & 0x8) && (b & 0x8) || 
(((a & 0x8) || (b & 0x8)) && ((a & 0x4) && (b & 0x4))) ||
(((a & 0x8) || (b & 0x8)) && ((a & 0x4) || (b & 0x4)) && ((a & 0x2) && (b & 0x2))) ||
(((a & 0x8) || (b & 0x8)) && ((a & 0x4) || (b & 0x4)) && ((a & 0x2) || (b & 0x2)) && ((a & 0x1) && (b & 0x1)))
) {
  // overflow
}
person troutinator    schedule 26.01.2011