Как стать автором
Обновить

Чему равно выражение -3/3u*3 на С++? Не угадаете. Ответ: -4. Приглашаю на небольшое расследование

Совершенный код *C++ *Компиляторы *IT-стандарты *Законодательство в IT
Из песочницы

Всё гораздо серьёзнее. Вот пример для проверки:

#include <iostream>

int main()
{
    std::cout << "-3/3u*3 = " << int(-3/3u*3) << "\n";
}

Посмотреть результат можно тут.

Или попробуйте поиграться с этим примером здесь или здесь.

Вообще-то мне не удалось найти хоть какой-то компилятор С++, который бы выдавал результат отличный от -4. Даже старый GCC-4.1.2, clang-3.0.0 или Borland C 1992 года. Также заметил, что результат одинаковый и для константы, вычисляемой в момент компиляции и для времени выполнения.

Предлагаю внимательно рассмотреть результат выражения -3/3u*3.

Если убрать приведение к типу intв примере выше, то получим 4294967292 или 0xFFFFFFFС(-4). Получается, что компилятор на самом деле считает результат беззнаковым и равным 4294967292. До этого момента я был свято уверен, что если в выражении используется знаковый тип, то и результат будет знаковым. Логично же это.

Если посмотреть откуда берется -4 вместо -3, посмотрим внимательней на ассемблерный код примера, например здесь.

Пример изменю, чтобы результат вычислялся не в момент компиляции, а в момент выполнения:

int main()
{
    volatile unsigned B = 3;
    int A = -3/B*3;
}

Для x86-64 clang 12.0.0 видим, что используется беззнаковое деление, хотя числитель откровенно отрицательное -3:

        mov     dword ptr [rbp - 4], 3    // B = 3
        mov     ecx, dword ptr [rbp - 4]
        mov     eax, 4294967293
        xor     edx, edx
        div     ecx                       // беззнаковое деление !!
        imul    eax, eax, 3               // знаковое умножение
        mov     dword ptr [rbp - 8], eax

Для x64 msvc v19.28 тот же подход к делению:

        mov     DWORD PTR B$[rsp], 3      // B = 3
        mov     eax, DWORD PTR B$[rsp]
        mov     DWORD PTR tv64[rsp], eax
        xor     edx, edx
        mov     eax, -3                             ; fffffffdH
        mov     ecx, DWORD PTR tv64[rsp]
        div     ecx
        imul    eax, eax, 3
        mov     DWORD PTR A$[rsp], eax

Получается, что для деления беззнакового числа на знаковое используется БЕЗЗНАКОВАЯ операция деления процессора div. Кстати, следующая команда процессора, это правильное знаковое умножение imul. Ну явный баг компилятора. Банальная логика же подсказывает, что знаковый тип выиграет в приведении типа результата выражения если оба знаковый и беззнаковый типы используются в выражении. И для знакового деления требуется знаковая команда деления процессора idiv, чтоб получить правильный результат со знаком.

Проблема еще и в том, что число 4294967293 не делится на 3 без остатка: 4294967293 = 1431655764 * 3 + 1 и при умножении 1431655764 обратно на 3, получаем 4294967292 или -4. Так что прикинуться веником и считать, что 4294967293 это то же -3, только вид сбоку, для операции деления не прокатит.

Двоично-дополнительное представление отрицательных чисел.

Благодаря представлению чисел в двоично-дополнительном виде, операции сложения или вычитания над знаковыми и беззнаковыми числами выполняются одной и той же командой процессора (add для сложения и sub для вычитания). Процессор складывает (или вычитает) только знаковое со знаковым или только беззнаковое с беззнаковым. И для обоих этих операций используется одна команда add (или sub) и побитово результат будет одинаковый (если бы кто-то решил сделать раздельные операции сложения для знаковых и беззнаковых типов). Различие только во флагах процессора. Так что считать знаковое беззнаковым и складывать их оба как беззнаковых корректно и результат будет побитово правильным в обоих случаях. Но для деления и умножения этот подход в корне неправильный. Процессор внутри использует только беззнаковые числа для деления и умножения и результат приводит обратно в знаковое с правильным признаком знака. И для этого процессор использует разные команды для знакового (idiv) и беззнакового деления (div) и так же и для умножения (imul и соответственно mul).

Я когда обнаружил, что используется беззнаковое деление, решил, что это бага компилятора. Протестировал много компиляторов: msvc, gcc, clang. Все показали такой же результат, даже древние трудяги. Но мне довольно быстро подсказали, что это поведение описано и закреплено в самом стандарте.

Действительно, стандарт говорит об этом прямо:

Otherwise, if the unsigned operand's conversion rank is greater or equal to the conversion rank of" "the signed operand, the signed operand is converted to the unsigned operand's type.

Иначе, если ранг преобразования беззнакового операнда больше или равен рангу преобразования знакового операнда, то знаковый операнд приводится к типу беззнакового операнда.

Вот где оказывается собака зарыта: "the signed operand is converted to the unsigned operand's type"!! Ну почему, почему, Карл!! Логичнее наоборот: "the unsigned operand is converted to the signed operand's type", разумеется при соблюдении ранга преобразования. Ну вот как -3 представить беззнаковым числом?? Наоборот кстати можно.

Интересная получается сегрегация по знаковому признаку!

Заметил, что это правило почему-то работает только для операции деления, а операция умножения вычисляется правильно.

Проверим на ассемблере здесь этот пример:

int main()
{
    volatile unsigned B = 3;
    int C = -3*B;
}
Вот ассемблерный код:

mov dword ptr [rbp - 4], 3 mov eax, dword ptr [rbp - 4] imul eax, eax, 4294967293 mov dword ptr [rbp - 8], eax

Стандарт ничего не говорит о неприменимости этого правила для операции умножения. И деление и умножение должны быть БЕЗЗНАКОВЫМИ.

UPD: В комментариях заметили, что IMUL богаче по вариантам использования, чем MUL. Да и результаты у них бывают одинаковые с отбрасыванием. Так что IMUL тут используется совсем не потому, что это правильно по логике.

Я подумал, что что-то в стандарте сломалось и надо срочно это исправить. Написал письмо напрямую в поддержку Стандарта со всеми моими выкладками и предложением поправить это странное правило стандарта пока еще не поздно.

Ага! Наивный!

Мне ответил любезный молодой сотрудник из Стандарта и подтвердил, что мои выкладки правильны, логика на моей стороне, но поведение компиляторов полностью согласуется со Стандартом и само правило менять не будут, так как оно такое древнее, что непонятно кто и когда его ввел (сотрудник сказал, что искал автора, но не нашел) и поэтому его, как святую корову, трогать никто не будет, хотя вроде логично было бы исправить. Ну и милостиво разрешил поведать эту историю миру. О чем и пишу.

Хоть это исследование и было больше года назад, я до сих пор под впечатлением от многих вещей в этой истории:

  • Как я не натыкался на это раньше? Не один десяток лет интенсивно кодирую на С и С++ с погружением в ассемблер, но только сейчас споткнулся на неё. Хотя может и натыкался ранее, но не мог поверить что причина именно в этом.

  • Ассемблер я выучил раньше С и поэтому всегда считал С удобной заменой Ассемблера. Но правила работы процессоров неизменны и даже языки высокого уровня им следуют.

Интересно, что это правило всё же не работает и для операций с указателями. С ними нет такого поведения. Видать понимают разработчики компиляторов, что иначе рухнет очень многое. Посмотрите этот пример здесь:

int main()
{
    const unsigned a[] = {3,4,5,6,7};
    unsigned p = (&a[0] - &a[3])/3u*3;    // -3
    unsigned b = -3/3u*3;   // -4
}

Хоть я и понимаю, что могу ошибаться в логике работы этого мира, но задумайтесь, в следующий раз садясь в современный, нашпигованный вычислительной логикой самолёт (или автомобиль), а не сработает ли вдруг не оттестированный кусок кода в какой-то редкой нештатной ситуации, и не выдаст ли он -4 вместо элементарных -3, и не постигнет ли его участь подобная Boeing 737 MAX?

Учитывая, что сейчас кода на С++ производится гораздо больше, чем его успевают покрывать тестами, надежда, что будет отловлена такая базовая операция, тает ниже плинтуса.

Ошибка в команде просессора FDIV у Интела

Помните, в начале 2000-х была выявлена ошибка с вычислением в команде FDIV у Интела. Там было различие в 5 знаке после запятой в какой-то операции деления. Какой был шум тогда!!
Но исправили оперативно и быстро. В компиляторы добавили условный флаг для обхода этой команды. Интел срочно исправил логику в кристалле и выпустил новые чипы.

И это всего лишь 5-й знак после запятой! Многие его даже и не заметили, подумаешь, мелочь какая! А тут -4 вместо -3 и считаем знаковое беззнаковым и вместо -3 имеем еще и 4294967292! И тишина в ответ! И в этой тишине тихо падают Боинги.

Предвижу возражение, что есть рекомендация использовать преимущественно беззнаковый тип. Понимаю, с таким правилом Стандарта по другому никак. Но как -4 в беззнаковое перевести, и чтоб всё остальное работало? И почему на других языках и всех процессорах не надо этими танцами с бубном заниматься, а в С++ надо? И что делать с константными выражениями, вычисляемыми компилятором? Вместо элегантных выражений, в которых мы уверены, надо записывать их с оглядкой, чтоб у компилятора небыло изжоги!

Так же найдутся, кто возразит, что ничего нельзя менять, поздно уже, много кода написано, и если в нём есть костыли, то он рухнет. Новые ошибки, они потом будут, а старые - они святое и уже превратились в знакомые фичи.

Как хорошую подсказку познавательно добавить предупреждение в компилятор когда он применяет это правило из Стандарта: "Signed value is intentionally converted to unsigned value. Sorry for crashing one more airplane. Have a nice flight!" Вот удивимся тогда, как мало мы тестируем и как много нам открытий чудных приносит компилятор друг.

Можно еще исправить Стандарт, ограничив правило только операциями сложения и вычитания. Как компромис. Но это крайне маловероятно в этой Вселенной. Да и Боингов еще много летает.

Представьте студента (С) на экзамене у преподавателя по информатике (П) в ВУЗе.

- П: Хорошо, последний вопрос на 5. Можно ли привести знаковое число к беззнаковому типу?
- С: Хе, можно. НУЖНО! Обязательно НУЖНО! Ставте 5, я пойду.
- П: Как НУЖНО?? О_О. Подумайте. Как можно представить, например, -4 беззнаковым числом? - С: Чего тут думать! Стандарт С++ сказал, что НУЖНО, значит НУЖНО и точка. А то что -4 станет беззнаковым очень большим числом - это уже ни печалька Стандарта, ни моя. - П: Подумайте еще раз. Вы на экзамене по информатике и вас спрашивают о базовых вещах, которые общие для всех языков программирования и процессоров, а не только для С++. - С: Чего вы пристали к мне со своими языками и процессорами. У меня в билете вопрос про С++, вот я про С++ и отвечаю. А вы про какой то там Ассемблер, базовые вещи, языки программирования! Стандарт С++ сказал, компилятор сделал, я ответил! У вас есть вопросы к Стандарту про базовые вещи, вот ему их и задавайте, а я ответил правильно! - П: Да уж. Подстава конкретная.

UPD: Провёл еще расследование. Спасибо комментаторам. Их как всегда читать очень интересно и познавательно. Для этого и опубликовано. Выражайте свое мнение!
Вот пример кода, где в операции деления участвуют числа a и -a в разных комбинациях и с декларацией явно unsigned. Результат ожидается быть -1. Из 15 примеров только 2 вернули -1, 3 вернули 4294967295, 6 - 0, остальные - разные числа.

результаты примера:

-1/1 = -1
1/-1 = -1
1u/-1 = 0
-1/1u = 4294967295
-1u/1 = 4294967295
1u/-1 = 0
2u/-2 = 0
3u/-3 = 0
4u/-4 = 0
5u/-5 = 0
-1/1u = 4294967295
-2/2u = 2147483647
-3/3u = 1431655764
-4/4u = 1073741823
-5/5u = 858993458

Вот еще пример кода, где знак - переносится к разным литералам и в результате имеем 3 разных ответа, хотя ответ не должен меняться по арифметической логике:

int main()
{
    constexpr auto s1 = -3/3u*3;   // -4
    constexpr auto s2 = 3u/-3*3;   // 0
    constexpr auto s3 = 3/3u*-3;   // -3
}
//test here: https://godbolt.org/

UPD: Меня удивляет мнение комментаторов, что если в толстом талмуде написано, что отрицательное число надо переводить в беззнаковое, то значит надо переводить. Даже если это нарушает элементарные арифметические правила и результат сильно не отличается от показаний давления в Марианской впадине! Всё корректно и по талмуду. И с картинками из талмуда совпадает. Еще наши деды этим талмудом пользовались, и по нему преподают в Университетах мира! В нём нет ошибки, ибо он всегда прав. А если не нравится талмуд - ищите другую религию. Выглядит так, будто пишу это не на ИТ форуме, а на эзотерическом.

Задайте себе вопрос - кто ввёл эти правила и что за ними стоит? Изначально их не было. Они появились позже, но искать причину никто не хочет, очень многих устраивает слепая вера в непреклонность писаний. А ошибки появляются, если талмудом неправильно пользоваться. Но талмуд всегда прав!

Ты unsigned туда не используй, а то DIV башка упадёт, совсем -4 будешь.

Как в анекдоте про целибат

Монах решил узнать откуда появился целибат. Долго всех расспрашивал, все отвечали, что всегда так было, значит так и должно быть. Наконец он залез в хранилище и пропал там надолго. Вспомнили о нём, спустились в хранилище и видят монаха бьющегося в истерике головой об стену и с отчаянием повторяющего:

It was celebrate, not celibate.
Было изначально празднуйте, а не целибат.

Теги:
Хабы:
Всего голосов 115: ↑101 и ↓14 +87
Просмотры 29K
Комментарии Комментарии 200