Любопытная арифметическая ошибка- 255x256x256x256=18446744073692774400

Я столкнулся со странной вещью, когда программировал под c++. Речь идет о простом умножении.

Код:

unsigned __int64 a1 = 255*256*256*256;
unsigned __int64 a2= 255 << 24; // same as the above

cerr()<<"a1 is:"<<a1;
cerr()<<"a2 is:"<<a2;

интересно результат такой:

a1 is: 18446744073692774400 
a2 is: 18446744073692774400 

тогда как это должно быть: (использование калькулятора подтверждает)

4278190080

Кто-нибудь может сказать мне, как это возможно?


person Hamid Bazargani    schedule 20.09.2012    source источник
comment
Это называется неопределенным поведением   -  person Tony The Lion    schedule 20.09.2012
comment
Нешуточные страсти по рейтингу постов :) От -3 до 2 и обратно за 5 секунд.   -  person Ivan Akulov    schedule 20.09.2012
comment
Не понимаю, почему это получило 8 голосов...   -  person    schedule 20.09.2012
comment
@ H2CO3: Потому что это неочевидная языковая причуда, которая очень интересна, а не потому, что вопрос хорошо сформулирован или исследован...   -  person Xeo    schedule 20.09.2012
comment
@ H2CO3: Да, давайте больше никогда ничего не писать на языке, который мы не понимаем на 110%. Вы понимаете, не так ли, что если бы мы придерживались такого мышления, мы никогда не узнали бы ничего нового?   -  person cHao    schedule 20.09.2012
comment
Раздражающая вещь в компиляторах C++ заключается в том, что их использование без включения предупреждений позволит вам сделать массу ошибок, которых вам не следует делать. Когда я компилирую этот код в GCC с g++ -Wall -Wextra -pedantic, компилятор довольно четко говорит мне: предупреждение: целочисленное переполнение в выражении [-Woverflow]. Microsoft Visual Studio также диагностирует эту проблему: предупреждение C4307: '*': целочисленное переполнение константы. Я надеюсь, что это послужит уроком для компиляции с предупреждениями в будущем.   -  person R. Martinho Fernandes    schedule 20.09.2012
comment
Что-то вроде того же: #comment16802182_12487923" title="почему происходит переполнение при расчете в зависимости от типа данных, когда тип whe%23comment16802182_12487923"> stackoverflow.com/questions/12487923/   -  person chris    schedule 20.09.2012
comment
@R.MartinhoFernandes Для умножения мой g++ (4.5.1, да, старый) предупреждает с уровнем предупреждения по умолчанию.   -  person Daniel Fischer    schedule 20.09.2012
comment
Другим способом избежать переполнения может быть использование литеральных суффиксов. В зависимости от вашего компилятора 255ULL * 256 * 256 * 256 может работать.   -  person aschepler    schedule 20.09.2012
comment
@aschepler Мало того, что должен согласно стандарту.   -  person Daniel Fischer    schedule 20.09.2012
comment
@DanielFischer: unsigned long long гарантированно имеет не менее 64 бит? (Правда, было бы глупо, если бы компилятор поддерживал тип __int64 и не делал его псевдонимом для long long.)   -  person aschepler    schedule 20.09.2012
comment
@DanielFischer: следовательно, в зависимости от вашего компилятора, поскольку все все еще заняты реализацией текущего стандарта. unsigned long long отсутствует в C++03, поэтому для его использования вам потребуется либо специфичное для компилятора расширение для C++03, либо (на данный момент) специфичная для компилятора частичная реализация C++11. На практике все имеют long long.   -  person Steve Jessop    schedule 20.09.2012
comment
@SteveJessop Ах, да, я забыл, насколько отстающим был C ++ в этом отношении.   -  person Daniel Fischer    schedule 20.09.2012
comment
@aschepler: минимальное соответствующее значение ULLONG_MAX равно 18446744073709551615, что соответствует стандарту не менее 64 бит.   -  person Steve Jessop    schedule 20.09.2012


Ответы (5)


 255*256*256*256

все операнды int вы переполняете int. Переполнение целого числа со знаком — это неопределенное поведение в C и C++.

ИЗМЕНИТЬ:

обратите внимание, что выражение 255 << 24 во втором объявлении также вызывает неопределенное поведение, если ваш тип int равен 32-bit. 255 x (2^24) — это 4278190080, которое не может быть представлено в виде 32-bit int (максимальное значение обычно равно 2147483647 на 32-bit int в дополнительном представлении до двух).

И C, и C++ говорят для E1 << E2, что если E1 имеет положительный тип со знаком и что E1 x (2^E2) не может быть представлено в типе E1, программа вызывает неопределенное поведение. Здесь ^ — математический оператор степени.

person ouah    schedule 20.09.2012
comment
Спасибо, сработало с unsigned __int64 a1 = 255*256*256; а1=а1*256; - person Hamid Bazargani; 20.09.2012
comment
просто мое любопытство, а должен ли int64 иметь 64 бита? и 255*256*256*256 = ff 00 00 00 и является 32-битным числом - person user902383; 20.09.2012
comment
@ user902383: Эти 255 и 256 являются целыми числами. Таким образом, С++ выполняет все промежуточные шаги с целыми числами (которые, скорее всего, 32-битные). Численно это заканчивается 0xFF000000. Преобразуйте это в 64-битное со знаком, и вы получите 0xFFFFFFFFFF000000 (расширение знака). Это всего лишь один из возможных способов, но он, безусловно, самый распространенный. - person cHao; 20.09.2012
comment
Разве это не отличается от C, где тип литерала определяется его размером? - person rubenvb; 20.09.2012
comment
@rubenvb: AFAIK, даже в C литералы целых чисел являются целыми числами, если вы специально не укажете, что они должны быть другими (через приведение или суффикс). Они просто преобразуются в нужный размер по мере необходимости, что в данном случае происходит после выполнения всех математических операций. - person cHao; 20.09.2012
comment
@cHao Нет, начиная с C99, тип определяется размером, первым в списке (int, long int, long long int для десятичных констант без суффикса, плюс соответствующие типы unsigned для восьмеричных или шестнадцатеричных констант; минус типы, исключенные суффиксом) константа вписывается в тип. - person Daniel Fischer; 20.09.2012
comment
В любом случае, 256 гарантированно имеет тип int, так как он подходит для int. Умножение его на что-то еще не меняет этого, все литералы маленькие. - person Steve Jessop; 20.09.2012
comment
Можно было бы утверждать, что все умножение является постоянным литералом, но я уверен, что ошибаюсь. Если бы только C(++) был разработан, чтобы быть хорошим, он очень применим здесь. - person rubenvb; 20.09.2012
comment
@rubenvb: да, вы не можете утверждать это на основе стандарта, потому что определение литерала в стандарте - это простой вопрос синтаксиса, и 256*255 не так :-) - person Steve Jessop; 20.09.2012
comment
@rubenvb Это постоянное выражение, и его переполнение делает программу неправильной. - person Daniel Fischer; 20.09.2012

Ваши литералы int. Это означает, что все операции фактически выполняются на int и быстро переполняются. Это переполненное значение при преобразовании в 64-битное целое число без знака является значением, которое вы наблюдаете.

person Puppy    schedule 20.09.2012
comment
Фундаментальная ошибка ОП распространена гораздо шире, чем этот пример: это ошибочное предположение, что тип левой стороны каким-то образом излучает магические силы на правой стороне и заставляет ее ясновидяще изменять поведение. - person Kerrek SB; 20.09.2012
comment
@KerrekSB Давай. Люди просто не ожидают переполнения с конца 8-битной эры, и вполне разумно ожидать, что литералы (или выражения только литералов) будут печататься автоматически. - person Potatoswatter; 20.09.2012
comment
@Potatoswatter: я думаю, было бы довольно безумно, если бы тип выражения зависел от значений его составляющих... как бы вы вообще это указали? Какой тип 256 * n? - person Kerrek SB; 20.09.2012
comment
@KerrekSB, следовательно, только литералы. Но обычно (или хорошей практикой, ИМХО) указывается большое постоянное число как произведение нескольких меньших. Такое бывает в реальной жизни. - person Potatoswatter; 20.09.2012
comment
@KerrekSB, разве Пайтон этого не делает? Я думаю, что видел что-то об обновлении типа при переполнении. - person chris; 20.09.2012
comment
@Potatoswatter: я знаю, что вы имели в виду только литералы, но опять же, как бы вы это уточнили? Мне кажется, вы попали бы в передрягу. - person Kerrek SB; 20.09.2012
comment
@chris: да, Python делает это, динамически выделяя достаточно памяти для значения. Это слишком тяжело для C. - person Steve Jessop; 20.09.2012
comment
@Kerrek: я не думаю, что было бы сложно определить выражения, включающие только литералы, не сложнее, чем определение целочисленного константного выражения в C++. Но даже если бы стандарт делал это, кто-то захотел бы другой частный случай, когда тип другой, и правила снова усложнились бы. Кстати, в одном случае левая сторона излучает магическую силу над правой, а именно присваивает указатель функции или функции-члена из перегруженного имени. Копните достаточно глубоко, и даже ошибочные предположения могут стать ориентиром в особых случаях ;-) - person Steve Jessop; 20.09.2012

Возможно, стоит объяснить, что произошло, чтобы получить число 18446744073692774400. С технической точки зрения, написанные вами выражения вызывают «неопределенное поведение», и поэтому компилятор мог получить в результате что угодно; однако, предполагая, что int является 32-битным типом, что в настоящее время почти всегда так, вы получите тот же «неправильный» ответ, если напишете

uint64_t x = (int) (255u*256u*256u*256u);

и это выражение не вызывает неопределенное поведение. (Преобразование из unsigned int в int связано с поведением, определяемым реализацией, но поскольку за многие годы никто не создал ЦП с дополнением до единицы или процессором со знаком и величиной, все реализации, с которыми вы, вероятно, столкнетесь, точно определяют его. точно так же.) Я написал приведение в стиле C, потому что все, что я здесь говорю, в равной степени относится к C и C++.

Во-первых, давайте посмотрим на умножение. Я пишу правую часть в шестнадцатеричном формате, потому что так легче увидеть, что происходит.

255u * 256u               = 0x0000FF00u
255u * 256u * 256u        = 0x00FF0000u
255u * 256u * 256u * 256u = 0xFF000000u (= 4278190080)

Этот последний результат, 0xFF000000u, имеет старший бит набора 32-битных чисел. Следовательно, приведение этого значения к 32-битному типу signed приводит к тому, что оно становится отрицательным, как если бы из него было вычтено 232 (это операция, определяемая реализацией, о которой я упоминал выше). ).

(int) (255u*256u*256u*256u) = 0xFF000000 = -16777216

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

Теперь, когда вы присваиваете -16777216 переменной uint64_t, она преобразуется обратно в беззнаковую как если бы путем добавления 264. (В отличие от преобразования без знака в знак, эта семантика предписана стандартом.) Это действительно изменяет битовый шаблон, устанавливая все старшие 32 бита числа в 1 вместо 0, когда вы ожидал:

(uint64_t) (int) (255u*256u*256u*256u) = 0xFFFFFFFFFF000000u

А если записать 0xFFFFFFFFFF000000 в десятичном виде, получится 18446744073692774400.

В качестве заключительного совета: всякий раз, когда вы получаете «невозможное» целое число из C или C++, попробуйте распечатать его в шестнадцатеричном формате; таким образом гораздо легче увидеть странности арифметики фиксированной ширины с дополнением до двух.

person zwol    schedule 20.09.2012
comment
Преобразование в беззнаковые типы предписано стандартом (4.7. в С++ 03, возможно, где-то аналогично в С++ 11; 6.3.1.3 в C99 и C11) как сокращение по модулю 2^WIDTH. - person Daniel Fischer; 20.09.2012

Ответ прост - переполнен.

person Lingfeng Xiong    schedule 21.09.2012

Здесь произошло переполнение int, и когда вы назначаете его беззнаковому int64, оно преобразуется в 18446744073692774400 вместо 4278190080.

person Rahul    schedule 21.09.2012