Проверка переполнения в знаковых сложениях и абелевых группах

Я читал о том, почему следующий код глючит:

int tadd_ok ( int x, int y ) {  
    int sum = x + y;  
    return ( sum - x == y ) && ( sum - y == x );  
}

Объяснение заключалось в том, что сложение дополнения до двух образует абелеву группу, поэтому выражение
(x + y) - x оценивается как y независимо от того, переполняется ли сложение.
(То же самое для (x + y) - y), которое будет оцениваться как x).

Я не понимаю это объяснение или ссылку на абелеву группу. Сложение с дополнением до двух в основном является беззнаковой арифметикой по модулю, которая «преобразуется» в дополнение до двух, верно?
Так, например, если у нас есть 4 бита, мы имеем диапазон [-8, 7].
В примере, если бы у нас было x = 7 и y = 6 результат переполняется до 6. И это не равно ни y, ни x.
Так почему же объяснение, что равенство всегда справедливо независимо от переполнения?


c types integer integer-overflow integer-arithmetic
person Cratylus    schedule 21.09.2014    source источник
comment
Это верно для целых чисел без знака, для целых чисел со знаком (например, int) переполнение вызывает неопределенное поведение.   -  person ouah    schedule 22.09.2014
comment
@ouah:Когда ты говоришь, что это правда, ты имеешь в виду мой ...Two's complement addition is basically unsigned modulo arithmetic that is "converted" to two's complement, right?   -  person Cratylus    schedule 22.09.2014
comment
Я имею в виду (x + y) - x оценку x.   -  person ouah    schedule 22.09.2014

Ответы (2)


arrow_upward
4
arrow_downward

«Абелева» группа просто означает, что порядок добавления элементов не имеет значения — (a+b)+c = a+(b+c) и (a+b) == (b+a).

Это верно для целых чисел в C. Технически верно, поскольку @ouah указывает, что переполнение не определено, но это необходимо для легкой поддержки стандарта C на процессорах, которые не используют двойную математику. Большинство делает.

На них, если в компиляторе не происходит что-то очень странное (или не очень странное, но оптимизированное — спасибо @ouah), беззнаковая математика будет функционировать как абелева группа.

В вашем примере 7+6 = 0111 + 0110 == 1101 равно -(0010+1) = -3. Отрицательные числа «считаются вниз» в двоичной системе с дополнительным знаком до двух: 1111 равно -1. Вычитание обратно дает 1010, или 0101+1 = 6.

person BadZen    schedule 21.09.2014
comment
это сделано для легкой поддержки стандарта C на процессорах, которые не используют двойную математику. Большинство так и делают. Современные компиляторы C активно выполняют оптимизацию, основанную на идее, что подписанное переполнение не определено. - person ouah; 22.09.2014
comment
Беззнаковая математика всегда будет функционировать как группа — этого требует стандарт. Математика со знаком не требуется спецификацией C, но большинство процессоров используют дополнение до 2, которое представляет собой группу. К сожалению, спецификация C не требует, чтобы компилятор использовал машинные операции дополнения до 2 во всех случаях - оптимизатор может сделать что-то еще, когда происходит переполнение. - person Chris Dodd; 22.09.2014
comment
@ouah - Интересно. Можете ли вы привести цитату и/или показать нам программу, скомпилированную в gcc, которая производит такое поведение? Я никогда этого не видел. - person BadZen; 22.09.2014
comment
@BadZen: 1) Если (a + b) может переполниться, то как порядок добавления не имеет значения? 2) 1011 пока -3 в порядке. Я потерял тебя в ...Subtracting back yields 1010 Что это значит? У нас -3. Что это за вычитание назад? - person Cratylus; 22.09.2014
comment
Вычитание назад == оценка первого выражения слева в строке возврата выше. Подумайте об этом так: переход к знаковому от беззнакового в системе дополнения до 2 из n битов похож на оценку обратимой карты, которая отправляет [0..2^{n-1}-1] в [0..2^{n -1}-1] и от [2^{n-1}..2^n-1] до [-2^{n-1}..-1] по порядку. То есть f(x) = x для первой ветви и f(x) = -(2^n-x) для второй. Таким образом, вы можете легко проверить заявленные мной коммутативные и ассоциативные свойства (т.е. абелевость). - person BadZen; 22.09.2014
comment
@BadZen Пример из реальной жизни: int foo(int a) { return (x * 10) / 10; }. Скомпилируйте с gcc -O0 и с -O3. Вычислите, например, foo(INT_MAX);. С -O3 (x * 10) / 10 складывается в x, используя неопределенное поведение подписанных переполнений. - person ouah; 22.09.2014
comment
@BadZen:Subtracting back yields 1010, or 0101+1 = 6. Но это -3-7=-10=10110, которое становится 0110 (усекается до 4 бит), что равно 3, что не равно x. Почему вычитание обратно дает 1010? Также 1010 - это -6, а не 6, как вы упомянули. - person Cratylus; 22.09.2014
comment
@BadZen: Вы правы. Виноват. 0110 равно 6. Но что такое 1010 в вашем ответе: ...yields 1010, or 0101+1 = 6. - person Cratylus; 22.09.2014
comment
Чтобы отрицать дополнительное число до двух, вы инвертируете двоичные цифры, а затем добавляете 1. 1010 — это исходное значение вычитания (вы можете позаимствовать немного из несуществующего пятого битового столбца, если хотите) - person BadZen; 22.09.2014
comment
@BadZen:To negate a two's complement number, you invert the binary digits and then add 1 Но это процесс для дополнения - person Cratylus; 22.09.2014
comment
Нет, вы не добавляете 1 для дополнения - нет смещения, потому что есть -0. Мы вообще не работаем в комплекте, как вы указали. Если вы работаете с комплементарной машиной, я не очень понимаю, как должно работать переполнение. Опять же, это не определено. - person BadZen; 24.09.2014

arrow_upward
1
arrow_downward

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

Это потому, что для исправления положительного переполнения (когда x + y > TYPE_MAX) нам нужно вычесть 2^n из суммы, а для исправления отрицательного (когда x + y < TYPE_MIN) нам нужно добавить 2^n (чтобы это показать, нужна куча математических выражений, поэтому я решил не включать их в ответ).

Следовательно, если x + y положительно переполнено, sum фактически равно x + y - 2^n. После этого, когда мы выполняем сравнение, мы вычитаем x из sum, что вызывает отрицательное переполнение, и, следовательно, sum - x фактически равно sum - x + 2^n. Таким образом, sum - x + 2^n = x + y - 2^n - x + 2^n = x. То же самое происходит и с другим предлогом.

person E. Shcherbo    schedule 19.01.2021