Целочисленная арифметика при наличии переполнения

Два 32-битных целых числа A и B обрабатываются для получения 32-битных целых чисел C и D в соответствии со следующими правилами. Какое из правил обратимо? т. е. возможно ли получить А и В при данных с и D во всех условиях?

A. C = (int32)(A+B), D = (int32)(A-B)

B. C = (int32)(A+B), D= (int32)((A-B)>>1)

C. C = (int32)(A+B), D = B

D. C = (int32)(A+B), D = (int32)(A+2*B)

E. C = (int32)(A*B), D = (int32)(A/B)

Несколько вопросов по целочисленной арифметике. Модульное сложение образует аматематическую структуру, известную как абелева группа. Как насчет сложения со знаком? Оно также коммутативно (вот где появляется «абелева» часть) и ассоциативно, образует ли это абелеву группу ?

Учитывая, что целочисленное сложение является коммутативным и ассоциативным, C, по-видимому, верно, потому что мы можем получить A с помощью (A+(BB)). А как насчет D? Можем ли мы предположить, что 2 * B = B + B ул. B = A+B+B-(A+B)?

А умножение сложнее, но я знаю, что его нельзя получить, если есть переполнение.


c c++ integer-arithmetic
person Joey.Z    schedule 06.10.2013    source источник
comment
Только unsigned целочисленные типы образуют группы относительно сложения в C и C++. Знаковое сложение обычно не может уже по той простой причине, что INT_MIN обычно не имеет обратного в обычном представлении 2дополнения.   -  person Jens Gustedt    schedule 06.10.2013
comment
@JensGustedt А как насчет конкретной проблемы выше?   -  person Joey.Z    schedule 06.10.2013
comment
Возьмите INT32_MIN вместо A и B, и реализация определяет, что произойдет в любом случае, поэтому ответа нет. У меня есть подозрение, что вы пытаетесь получить последовательный ответ на некорректное упражнение. Часто мы видим здесь такие упражнения, которые исходят от не очень хорошо информированных учителей, которые принимают дополнение до двух как должное и никогда не слышали о сигналах, которые можно подать в случае переполнения. Делайте такие вещи не с int32 (кстати, стандартный typedef называется int32_t), а с uint32_t. Откуда у вас эти вопросы?   -  person Jens Gustedt    schedule 06.10.2013
comment
@JensGustedt Письменный тест для стажера Microsoft. Но я видел это где-то еще.   -  person Joey.Z    schedule 08.10.2013
comment
@JensGustedt Я тебя не перестаю понимать. Этот вопрос спрашивает вас о том, какой из них может получить A и B даже при переполнении. Я думаю, что C прав в любом случае. Потому что сложение целых чисел коммутативно и ассоциативно. Таким образом, я могу получить A с помощью E = C - D = A + B - B = A и B с помощью C - E. Что вы думаете? И я принимаю D как правильный ответ, см. мои вопросы.   -  person Joey.Z    schedule 08.10.2013
comment
Нет, этот тест не имеет решения, как все пытаются доказать. Если есть переполнение, результат в лучшем случае определяется реализацией. Просто нет смысла задавать такие вопросы. Если это действительно то, что MS тестирует для своих стажеров, это снова доказывает, что они не имеют большого представления о C. Может быть, если вы измените вопрос на то, что было бы возможно с компилятором MS, это очень важно. конкретного компилятора, может быть ответ.   -  person Jens Gustedt    schedule 08.10.2013

Ответы (1)


arrow_upward
8
arrow_downward

Это цитата из 5 [expr] параграф 4:

Если во время вычисления выражения результат не определен математически или не находится в диапазоне представляемых значений для его типа, поведение не определено.

Что заставляет работать переполнение для целых чисел без знака, определено в 3.9.1 [basic.fundamental], параграф 4:

Целые числа без знака должны подчиняться законам арифметики по модулю 2n, где n — количество битов в представлении значения этого конкретного размера целого числа.

В основном это говорит о том, что вы не должны переполняться при использовании целочисленной арифметики со знаком. Если вы это сделаете, все ставки сняты. Это означает, что целые числа со знаком не образуют абелеву группу в C++.

person Dietmar Kühl    schedule 06.10.2013
comment
Но подписанное сложение коммутативно и ассоциативно. Этого недостаточно, чтобы образовать абелеву группу? И какие-либо предложения по конкретной проблеме выше (2-й вопрос)? - person Joey.Z; 06.10.2013
comment
@zoujyjs: правила должны применяться к любому значению в группе. Однако они явно неприменимы, например, для A == std::numeric_limits<int>::max() и B == 2, потому что A + B и A * B оба переполняются, что приводит к неопределенному поведению. - person Dietmar Kühl; 06.10.2013