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

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

}

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


c addition bit-manipulation
person Zach    schedule 06.10.2013    source источник
comment
Почему голосование против? Кажется, этого достаточно.   -  person Brian    schedule 07.10.2013

Ответы (1)


arrow_upward
2
arrow_downward

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

Затем вы определяете, какое значение переполнения должно быть возвращено в случае переполнения. Это можно сделать с помощью XOR 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 даст нам правильное значение.

person Yoctohan    schedule 07.10.2013