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

Question

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

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

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

Answer 1

Числа - ABCD и EFGH, ^ - И, | ИЛИ.

(A ^ E) | (B ^ F ^ (A | E)) | (C ^ G ^ (B | F) ^ (A | E)) | (Д ^ Н ^ (С | G) ^ (В | Р) ^ (А | Е))

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

Answer 2

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

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
}