Является ли отрицательное целое, суммированное с большим целым числом без знака, преобразованным в целое число без знака?

После того, как мне посоветовали прочитать «C++ Primer 5 ed Stanley B. Lipman», я этого не понимаю:

Страница 66. «Выражения, использующие беззнаковые типы»

unsigned u = 10;
int i = -42;
std::cout << i + i << std::endl; // prints -84
std::cout << u + i << std::endl; // if 32-bit ints, prints 4294967264

Он сказал:

Во втором выражении значение int -42 преобразуется в беззнаковое перед выполнением сложения. Преобразование отрицательного числа в беззнаковое происходит точно так же, как если бы мы попытались присвоить это отрицательное значение беззнаковому объекту. Значение «обтекает», как описано выше.

Но если я сделаю что-то вроде этого:

unsigned u = 42;
int i = -10;
std::cout << u + i << std::endl; // Why the result is 32?

Как видите, -10 не преобразуется в unsigned int. Означает ли это, что сравнение происходит до преобразования signed integer в unsigned integer?


person Alex24    schedule 14.01.2019    source источник
comment
Погуглите о двоичных числах и о том, как они представлены, в частности о знаках. Тогда все станет ясно.   -  person DeiDei    schedule 15.01.2019
comment
Какой результат вы ожидали вместо 32?   -  person Barmar    schedule 15.01.2019
comment
Спасибо всем, ребята. Ты разъясняешь мне это сейчас.   -  person Alex24    schedule 16.01.2019


Ответы (5)


-10 преобразуется в целое число без знака с очень большим значением, причина, по которой вы получаете маленькое число, заключается в том, что сложение возвращает вас назад. Для 32-битных целых чисел без знака -10 совпадает с 4294967286. Когда вы добавляете к этому 42, вы получаете 4294967328, но максимальное значение равно 4294967296, поэтому мы должны взять 4294967328 по модулю 4294967296, и мы получим 32.

person NathanOliver    schedule 14.01.2019
comment
Что я нахожу интересным в арифметике по модулю, так это то, что запутанными способами вы получаете тот же ответ, что и обычная арифметика. Это одна из причин, по которой можно оправдать поведение упаковки для обработки переполнения. - person Matthieu M.; 15.01.2019
comment
@MatthieuM. Свертка происходит только тогда, когда вы думаете о целых числах без знака как о числах. Тот факт, что добавление числа из класса эквивалентности 42 к числу из класса эквивалентности -10 дает значение из класса эквивалентности 32, не менее интуитивно понятен, чем подписанный результат IMO. - person Baum mit Augen; 15.01.2019
comment
Так просто и понятно спасибо. Один вопрос: почему short и char не повышаются до unsigned? - person Alex24; 16.01.2019
comment
@ Alex24 Пожалуйста. short и char повышаются до int, так как это наименьший встроенный тип, используемый математическими операторами. Единственное время, когда это может быть по-другому, это когда у вас есть unsigned char или unsigned short и он имеет тот же размер, что и int. Затем он будет повышен до unsigned int. - person NathanOliver; 16.01.2019
comment
@NathanOliver: Отлично! еще раз спасибо. Действительно понял вашу точку зрения. - person Alex24; 16.01.2019

Ну, я думаю, это исключение из "две ошибки не делают правильно" :)

Что происходит, так это то, что на самом деле под капотом есть два циклических обхода (беззнаковых переполнения), и окончательный результат оказывается математически правильным.

  • Во-первых, i преобразуется в беззнаковое, и в соответствии с поведением переноса значение равно std::numeric_limits<unsigned>::max() - 9.

  • Когда это значение суммируется с u, математическим результатом будет std::numeric_limits<unsigned>::max() - 9 + 42 == std::numeric_limits<unsigned>::max() + 33, что является переполнением, и мы получаем еще один цикл. Итак, окончательный результат 32.


Как правило, в арифметическом выражении, если у вас есть только беззнаковые переполнения (независимо от того, сколько) и если окончательный математический результат может быть представлен в типе данных выражения, то значение выражения будет математически правильным. Это следствие того факта, что целые числа без знака в C++ подчиняются законам арифметики по модулю 2n (см. ниже).


Важное замечание. Согласно С++ беззнаковая арифметика не переполняется:

§6.9.1 Фундаментальные типы [basic.fundamental]

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

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

Однако я оставлю «переполнение» в своем ответе, чтобы выразить значения, которые не могут быть представлены в обычной арифметике.

Кроме того, то, что мы в просторечии называем «обтеканием», на самом деле является просто арифметической модульной природой целых чисел без знака. Однако я буду использовать «обтекание» еще и потому, что его легче понять.

person bolov    schedule 14.01.2019
comment
Беззнаковая арифметика не переполняется. - person Baum mit Augen; 15.01.2019
comment
afaik это делает, и это хорошо определено - person bolov; 15.01.2019
comment
@BaummitAugen что? конечно переливается. Добавьте два больших целых числа без знака, вы не можете представить число, которое не соответствует формату числа. - person Garr Godfrey; 15.01.2019
comment
Нет. Он может представлять любое целое число, выбирая представителя своего класса эквивалентности, лежащего в [0, 2^NumBit - 1]. Переполнение происходит, когда некоторый результат не может быть представлен. Этого не может быть в беззнаковой арифметике. - person Baum mit Augen; 15.01.2019
comment
@GarrGodfrey Да, это может представлять результат. Вы неправильно понимаете арифметику, которую он реализует. - person Baum mit Augen; 15.01.2019
comment
Мы говорим о С++. unsigned int имеет фиксированный размер. Он не может расширяться бесконечно. - person Garr Godfrey; 15.01.2019
comment
@BaummitAugen числа без знака для переполнения/незаполнения. Они просто делают это четко определенным образом. - person NathanOliver; 15.01.2019
comment
@BaummitAugen Я пошел на стандарт, чтобы доказать свою точку зрения. Оказывается, я был неправ. Спасибо. - person bolov; 15.01.2019
comment
@GarrGodfrey Каждое целое число находится в некотором классе эквивалентности Z / n для любого натурального числа n. Конечных битов достаточно. - person Baum mit Augen; 15.01.2019
comment
если окончательный математический результат результат КАКОЙ операции? - person curiousguy; 15.01.2019
comment
@curiousguy любое арифметическое выражение. Я отредактировал, чтобы быть более ясным. Надеюсь, теперь это так. - person bolov; 15.01.2019
comment
немного нелепо утверждать, что потеря старших битов не считается переполнением только потому, что младшие биты все еще точны. - person Garr Godfrey; 15.01.2019
comment
@GarrGodfrey Я искал стандарт, и он действительно прав. Переполнения нет. И это потому, что целые числа без знака не представляют натуральные числа, но, как сказал Бауммит Оген, они представляют классы эквивалентности. - person bolov; 15.01.2019
comment
@bolov они представляют классы эквивалентности, тогда зачем кому-то использовать их для представления количества байтов, количества объектов в контейнере и т. д.? - person curiousguy; 15.01.2019
comment
@curiousguy, потому что они такие полезные - person bolov; 15.01.2019
comment
@bolov По крайней мере, с целыми числами со знаком компилятору разрешено останавливать программы, которые переполняются. Переполнение в большинстве случаев происходит непреднамеренно и является признаком ошибки. (Ошибка, которая легко может быть уязвимостью системы безопасности.) Определение переполнения с обтеканием иногда полезно, но может скрыть ошибки. Если люди полагаются на его определение, вы не сможете позже добавить режим отладки, который диагностирует его из-за ложных предупреждений. - person curiousguy; 15.01.2019
comment
@curiousguy Я слышал, как некоторые люди (эксперты) говорили, что использование циклического поведения для неподписанных было плохим решением задним числом. Однако их основной причиной была оптимизация, которую он запрещает. Они утверждали, что обычный неподписанный тип имеет неопределенное поведение при переполнении и существует какой-то другой тип данных, который имеет циклическое поведение. Но что есть, то есть. - person bolov; 15.01.2019
comment
@curiousguy тогда зачем кому-то использовать их для представления количества байтов, количества объектов в контейнере и т. д.? Несколько видных членов комитета считают именно это исторической ошибкой. channel9.msdn.com/Events/GoingNative/2013/ 9:50, 42:40, 1:02:50 - person Baum mit Augen; 15.01.2019

i на самом деле повышен до unsigned int.

Целые числа без знака в C и C++ реализуют арифметику в ℤ / 2nℤ, где n — количество битов в типе целого числа без знака. Таким образом, мы получаем

[42] + [-10] ≡ [42] + [2n - 10] ≡ [2n + 32] ≡ [32],

где [x] обозначает класс эквивалентности x в ℤ / 2nℤ.

Конечно, промежуточный шаг выбора только неотрицательных представителей каждого класса эквивалентности, хотя он и имеет место формально, не является необходимым для объяснения результата; непосредственный

[42] + [-10] ≡ [32]

тоже будет правильно.

person Baum mit Augen    schedule 14.01.2019
comment
Разве это не должно быть ℤ mod 2n? - person JAD; 15.01.2019
comment
@JAD Должно быть ℤ / 2ⁿ ℤ - person Eric Duminil; 15.01.2019
comment
@BaummitAugen: Не за что, я люблю Klugscheißing. - person Eric Duminil; 15.01.2019
comment
@EricDuminil И математика, и C ++ подходят для этого. = Д - person Baum mit Augen; 15.01.2019

«Во втором выражении значение int -42 преобразуется в беззнаковое до выполнения сложения»

Да, это правда

unsigned u = 42;
int i = -10;
std::cout << u + i << std::endl; // Why the result is 32?

Предположим, что мы находимся в 32 битах (это ничего не меняет в 64b, это просто для объяснения), это вычисляется как 42u + ((unsigned) -10), поэтому 42u + 4294967286u, и результат 4294967328u, усеченный в 32 бита, поэтому 32. Все было сделано в беззнаковом формате.

person bruno    schedule 14.01.2019

Это часть того, что замечательно в дополнительном представлении 2. Процессор не знает и не заботится о том, подписано число или нет, операции одинаковы. В обоих случаях расчет правильный. На самом деле имеет значение только то, как интерпретируется двоичное число постфактум при печати (могут быть и другие случаи, например, с операторами сравнения)

-10 in 32BIT binary is FFFFFFF6
42 IN 32bit BINARY is  0000002A

Складывая их вместе, для процессора не имеет значения, знаковые они или беззнаковые, результат: 100000020. В 32-битной системе 1 в начале помещается в регистр переполнения, а в С++ просто исчезает. В результате вы получите 0x20, что равно 32.

В первом случае все аналогично:

-42 in 32BIT binary is FFFFFFD6
10 IN 32bit binary is 0000000A

Сложите их вместе и получите FFFFFFE0

FFFFFFE0 как целое число со знаком равно -32 (десятичное число). Расчет правильный! Но, поскольку он печатается как беззнаковый, он отображается как 4294967264. Речь идет об интерпретации результата.

person Garr Godfrey    schedule 14.01.2019
comment
В качестве примечания: в x86 большинство арифметических операций устанавливают различные биты в регистр флагов, которые затем можно использовать, например, для выполнить ветвление. Например, сложение установит CF (флаг переноса), чтобы обозначить, что произошло неподписанное перенос, и/или OF (флаг переполнения), чтобы обозначить, что произошло переполнение со знаком, если вы считаете операнды подписанными. Была даже 1-байтовая инструкция INTO, которая генерировала программное прерывание, если был установлен OF, что могло помочь при отладке, но, к сожалению, не поддерживалось языками более высокого уровня и больше недоступно в 64-битном режиме. - person Arne Vogel; 15.01.2019
comment
С технической точки зрения ничто не требует представления с дополнением до 2. Просто модульно-арифметическое преобразование, указанное в стандарте, в точности эквивалентно использованию дополнения до 2 (в этом вы убедитесь, если выполните преобразование в системе со знаком-величиной или с дополнением до 1, если это правильно). - person Toby Speight; 15.01.2019
comment
реализация сумматора в комплименте 1 или величине знака очень сложна по сравнению с комплиментом 2. Не требуется, кроме здравомыслия. - person Garr Godfrey; 15.01.2019