Насыщенное целочисленное целочисленное сложение с только побитовыми операторами в C (HW)

Question

Для задания домашней работы мне нужно написать функцию на C, которая объединяет два знаковых целых числа, но возвращает INT_MAX, если бы было положительное переполнение и INT_MIN, если бы быть отрицательным переполнением. Я должен соблюдать очень строгие ограничения в отношении того, какие операторы я могу использовать. Все целые числа находятся в форме двух дополнений, правые сдвиги арифметичны, а целочисленный размер является переменным (я могу найти его с sizeof (int) < < 3). Я не могу использовать contitionals, циклы, операторы сравнения или кастинг. Я могу использовать только побитовые и логические операторы, сложение и вычитание, тесты равенства и целочисленные константы INT_MAX и INT_MIN.

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

int saturating_add(int x, int y){ 
    int w = sizeof(int)<<3; 
    int result = x+y; 
    int signX = (x>>w-1)&0x01;//Sign bit of X 
    int signY = (y>>w-1)&0x01;//Sign bit of Y 
    int resultSign = (result>>w-1)&0x01; //Sign bit of result 
    int canOverflow = ~(signX^signY); //If they're the same sign, they can overflow 
    int didOverflow = (resultSign^signX)&canOverflow; //1 if input signs are same and result sign different, 0 otherwise 

} 

Я пытаюсь следовать ответ изображенную Bitwise saturated addition in C (HW), но я застрял на той части, где я должен заполнить целое с тем же немного для всех, кроме бит знака (1 переходит в 0111..11, а 0 - 0000.00). Я не знаю, что такое «комбинация сдвигов и ОР».

Answer 1

Я думаю, вы неправильно поняли ответ. То, что вам нужно сделать, это расширить бит знака до всех бит, включая MSB. Это может быть достигнуто путем приема int, содержащего знаковый бит, например. didOverflow, и добавьте 1 к его дополнению.

Затем вы обнаружите, какое значение переполнения должно быть возвращено в случае переполнения. Это можно сделать с помощью XORing INT_MAX с расширенными signX (или signY, оба будут работать). Назовем это значение overflow. И, наконец, изменить overflow и result вроде этого:

overflow := (extended didOverflow) AND overflow 
result := (NOT (extended didOverflow)) AND result 

Теперь, после этих назначений, если расширенный didOverflow является 1 ... 1, тем overflow будет, очевидно, остается неизменным. result, с другой стороны, будет равна 0.

Но если didOverflow 0 ... 0, то справедливо обратное: overflow теперь 0, в то время как result остается неизменной.

В первом случае (где didOverflow был 1 ... 1, сигнализируя о переполнении), overflow OR result равно overflow. Во втором случае (где у нас нет переполнения), overflow OR result равно result. Таким образом, в любом случае, overflow OR result даст нам правильное значение.