Логический оператор NOT (!) Не будет работать с побитовым оператором

Question

Я пытаюсь определить, могу ли я вычислить сумму двух 32-битных целых чисел без переполнения, используя при этом только определенные побитовые и другие операторы. Таким образом, если целые числа x и y могут быть добавлены без переполнения, следующий код должен возвращать 1 и 0 в противном случае.

(((((x >> 31) + (y >> 31)) & 2) >> 1))

Тем не менее, он возвращает 0, когда он должен быть 1, и наоборот. Когда я использую логический оператор NOT (!) Или побитовый XOR (^) с 0x1, это не решает проблему.

!(((((x >> 31) + (y >> 31)) & 2) >> 1))

(((((x >> 31) + (y >> 31)) & 2) >> 1) ^ 0x1)

^ это не работает.

Заранее спасибо.

Answer 1

Это немного чище:

~(x & y) >> 31

Обновление

Комментарий Криса верен.весь этот код выполняет проверку того, что оба MSB установлены.

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

((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)

Первый раздел в скобках устанавливает MSB равным 0, а затем добавляет результат.Любой перенос окажется в MSB результата.Следующая битовая маска изолирует, что несут.Последний термин проверяет набор MSB на x или y, что приводит к общему переносу.Чтобы соответствовать спецификации в вопросе, просто сделайте:

~(((x & 0x7FFFFFFF) + (y & 0x7FFFFFFF)) & 0x80000000 & (x | y)) >> 31

Answer 2

Предположим, что оба числа являются целыми числами без знака. Если вы работаете со целыми числами со знаком, это будет немного сложнее, так как есть два способа переполнения: добавление двух больших положительных значений с добавлением двух больших отрицательных. В любом случае проверки старших значащих битов будет недостаточно, так как сложение передает бит переноса, вы должны принять это во внимание.

Для целых чисел без знака, если вы не хотите обманывать, есть простой способ:

 (x+y < x) || (x+y < y)

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

Вы также можете заметить, что для переполнения, по крайней мере, для одного из двух чисел должен быть установлен самый старший бит, равный 1. Следовательно, что-то подобное должно работать (будьте осторожны, не проверено), но это гораздо более сложно, чем в другой версии .

/* both Most Significant bits are 1 */
(x&y&0x80000000)        
/* x MSb is 1 and carry propagate */
 ||((x&0x80000000)&&(((x&0x7FFFFFFF)+y)&0x80000000))
/* y MSb is 1 and carry propagate */
 ||((y&0x80000000)&&(((y&0x7FFFFFFF)+x)&0x80000000))

Answer 3

Нет простого бит-арифметического теста на переполнение, потому что сложение включает перенос.Но существуют простые тесты на переполнение, которые не включают в себя вызов переполнения или переноса целых чисел без знака, и они даже проще, чем выполнение сложения и проверки на переполнение (что, конечно, неопределенное поведение для целых чисел со знаком):Для целых чисел без знака x и y: (x<=UINT_MAX-y)

Для целых чисел со знаком сначала проверьте, имеют ли они противоположные знаки.Если это так, добавление автоматически безопасно.Если они оба положительные, используйте (x<=INT_MAX-y).Если они оба отрицательны, используйте (x>=INT_MIN-y).

Answer 4

логично!у меня работает нормально.

me@desktop:~$ cat > so.c
#include <stdio.h>

void main() {
    int y = 5;
    int x = 3;
    int t;
    t = (((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
    t = !(((((x >> 31) + (y >> 31)) & 2) >> 1));
    printf("%d\n", t);
}
^D
me@desktop:~$ gcc -o so so.c
me@desktop:~$ ./so
0
1
me@desktop:~$ uname -a
Linux desktop 2.6.32-23-generic #37-Ubuntu SMP Fri Jun 11 07:54:58 UTC 2010 i686 GNU/Linux

Answer 5

Являются ли эти подписанные целыми числами случайно?Ваша логика выглядит так, как будто она подходит для целых чисел без знака (int без знака), но не для обычных целых чисел, поскольку в этом случае сдвиг сохранит знаковый бит.