Эффективное преобразование без знака в знак, позволяющее избежать поведения, определяемого реализацией

Я хочу определить функцию, которая принимает unsigned intаргумент as и возвращает аргументу, intсовпадающему по модулю UINT_MAX + 1.

Первая попытка может выглядеть так:

int unsigned_to_signed(unsigned n)
{
    return static_cast<int>(n);
}

Но, как известно любому юристу по языку, приведение беззнакового к подписанному для значений, превышающих INT_MAX, определяется реализацией.

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

Что касается странных машин ... Если нет подписанного int, совпадающего по модулю UINT_MAX + 1 с unsigned int, скажем, я хочу выбросить исключение. Если их несколько (я не уверен, что это возможно), скажем, мне нужен самый большой.

Хорошо, вторая попытка:

int unsigned_to_signed(unsigned n)
{
    int int_n = static_cast<int>(n);

    if (n == static_cast<unsigned>(int_n))
        return int_n;

    // else do something long and complicated
}

Меня не особо заботит эффективность, когда я не использую типичную систему с дополнением до двух, поскольку, по моему скромному мнению, это маловероятно. И если мой код станет узким местом во вездесущих знаково-величинных системах 2050 года, я готов поспорить, что кто-то сможет это понять и оптимизировать.

Эта вторая попытка довольно близка к тому, что я хочу. Хотя приведение к intопределено реализацией для некоторых входных данных, приведение обратно кunsigned гарантировано стандартом для сохранения значения по модулю UINT_MAX + 1. Таким образом, условное выражение действительно проверяет именно то, что я хочу, и оно не будет компилироваться ни в какую систему в любой системе, с которой я, вероятно, столкнусь.

Однако ... я все еще intвыполняю приведение к без предварительной проверки, будет ли он вызывать поведение, определяемое реализацией. По какой-то гипотетической системе в 2050 году он может делать неизвестно что. Допустим, я хочу этого избежать.

Вопрос: Как должна выглядеть моя «третья попытка»?

Подводя итоги, я хочу:

• Преобразование из беззнакового int в подписанное int
• Сохранить значение по модулю UINT_MAX + 1
• Вызвать только стандартное поведение
• Скомпилировать без операции на типичной машине с дополнением до двух с оптимизирующим компилятором

[Обновить]

Позвольте мне привести пример, чтобы показать, почему это нетривиальный вопрос.

Рассмотрим гипотетическую реализацию C ++ со следующими свойствами:

• sizeof(int) равно 4
• sizeof(unsigned) равно 4
• INT_MAX равно 32767
• INT_MINравно -2 ³² + 32768
• UINT_MAXравен 2 ³² - 1
• Арифметика по intмодулю 2 ³² (в диапазон INT_MINчерез INT_MAX)
• std::numeric_limits<int>::is_modulo правда
• Приведение без знака nк int сохраняет значение для 0 <= n <= 32767 и дает ноль в противном случае

В этой гипотетической реализации intкаждому unsignedзначению соответствует ровно одно значение (mod UINT_MAX + 1) . Так что мой вопрос будет четко определен.

Я утверждаю, что эта гипотетическая реализация C ++ полностью соответствует спецификациям C ++ 98, C ++ 03 и C ++ 11. Признаюсь, я не запомнил каждое слово из них ... Но думаю, что внимательно прочитал соответствующие разделы. Поэтому, если вы хотите, чтобы я принял ваш ответ, вы должны либо (а) указать спецификацию, которая исключает эту гипотетическую реализацию, либо (б) правильно ее обработать.

Действительно, правильный ответ должен соответствовать каждой гипотетической реализации, разрешенной стандартом. Это то, что по определению означает «вызывать только стандартное поведение».

Кстати, обратите внимание, что std::numeric_limits<int>::is_moduloздесь совершенно бесполезно по нескольким причинам. Во-первых, это может быть, trueдаже если преобразование без знака в знак не работает для больших значений без знака. С другой стороны, это может быть trueдаже система с дополнением до единицы или знак-величина, если арифметика просто модулирует весь диапазон целых чисел. И так далее. Если ваш ответ зависит от is_modulo, это неправильно.

[Обновление 2]

Ответ hvd научил меня кое-чему: моя гипотетическая реализация на C ++ для целых чисел не разрешена современным C. Стандарты C99 и C11 очень специфичны в отношении представления целых чисел со знаком; действительно, они допускают только дополнение до двух, дополнение до единицы и знаковую величину (раздел 6.2.6.2 параграф (2);).

Но C ++ - это не C. Как оказалось, этот факт лежит в основе моего вопроса.

Исходный стандарт C ++ 98 был основан на гораздо более старом C89, в котором говорится (раздел 3.1.2.5):

Для каждого из целочисленных типов со знаком существует соответствующий (но другой) целочисленный тип без знака (обозначенный ключевым словом unsigned), который использует тот же объем памяти (включая информацию о знаках) и имеет одинаковые требования к выравниванию. Диапазон неотрицательных значений целочисленного типа со знаком является поддиапазоном соответствующего целочисленного типа без знака, и представление одного и того же значения в каждом типе одинаково.

C89 ничего не говорит о наличии только одного знакового бита или о разрешении только дополнения до двух / дополнения до единицы / величины знака.

Стандарт C ++ 98 практически дословно принял этот язык (раздел 3.9.1, параграф (3)):

Для каждого из целочисленных типов со знаком существует соответствующий (но разный) целочисленный тип без знака : « unsigned char», « unsigned short int», « unsigned int» и « unsigned long int», каждый из которых занимает одинаковый объем памяти и имеет одинаковые требования к выравниванию (3.9 ) как соответствующий знаковый целочисленный тип; то есть каждый знаковый целочисленный тип имеет то же представление объекта, что и соответствующий ему беззнаковый целочисленный тип. Диапазон неотрицательных значений целочисленного типа со знаком является поддиапазоном соответствующего целочисленного типа без знака, и представление значения каждого соответствующего типа со знаком / без знака должно быть одинаковым.

Стандарт C ++ 03 использует практически идентичный язык, как и C ++ 11.

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

Итак, я снова утверждаю, что INT_MAX = 32767 с INT_MIN = -2 ³² +32768 разрешено. Если ваш ответ предполагает иное, он неверен, если вы не цитируете стандарт C ++, доказывающий, что я ошибаюсь.

Расширение ответа пользователя71404:

int f(unsigned x)
{
    if (x <= INT_MAX)
        return static_cast<int>(x);

    if (x >= INT_MIN)
        return static_cast<int>(x - INT_MIN) + INT_MIN;

    throw x; // Or whatever else you like
}

Если x >= INT_MIN(помните о правилах продвижения, INT_MINпреобразуется в unsigned), то x - INT_MIN <= INT_MAX, значит, переполнения не будет.

Если это не очевидно, взгляните на утверждение «Если x >= -4u, то x + 4 <= 3.» И имейте в виду, что оно INT_MAXбудет равно по крайней мере математическому значению -INT_MIN - 1.

В наиболее распространенных системах, где это !(x <= INT_MAX)подразумевается x >= INT_MIN, оптимизатор должен иметь возможность (а в моей системе может) удалить вторую проверку, определить, что два returnоператора могут быть скомпилированы в один и тот же код, а также удалить первую проверку. Сгенерированный список сборок:

__Z1fj:
LFB6:
    .cfi_startproc
    movl    4(%esp), %eax
    ret
    .cfi_endproc

Гипотетическая реализация в вашем вопросе:

• INT_MAX равно 32767
• INT_MIN равно -2 ³² + 32768

невозможно, поэтому не требует особого рассмотрения. INT_MINбудет равно либо -INT_MAX, либо -INT_MAX - 1. Это следует из представления C целочисленных типов (6.2.6.2), которое требует, чтобы nбиты были битами значений, один бит был битом знака, и допускает только одно представление ловушки (не включая представления, которые недействительны из-за битов заполнения), а именно тот, который в противном случае представлял бы отрицательный ноль / -INT_MAX - 1. C ++ не допускает никаких целочисленных представлений за пределами того, что позволяет C.

Обновление : компилятор Microsoft, по-видимому, этого не замечаетx > 10иx >= 11тестирует то же самое. Он генерирует желаемый код только в том случае, еслиx >= INT_MINон заменен наx > INT_MIN - 1u, который он может определить как отрицаниеx <= INT_MAX(на этой платформе).

[Обновление от спрашивающего (Немо), подробно рассказывающего о нашем обсуждении ниже]

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

Начнем с C ++ 11, раздел 18.3.3:

В таблице 31 описан заголовок <climits>.

...

Содержание такого же , как заголовок стандартной библиотеки C <limits.h>.

Здесь «Стандартный C» означает C99, спецификация которого строго ограничивает представление целых чисел со знаком. Они похожи на целые числа без знака, но с одним битом, предназначенным для «знака», и нулем или более битами, предназначенными для «заполнения». Биты заполнения не вносят вклад в значение целого числа, а знаковый бит вносит вклад только как дополнение до двух, дополнение до единицы или знаковая величина.

Поскольку C ++ 11 наследует <climits>макросы от C99, INT_MIN имеет значение -INT_MAX или -INT_MAX-1, и код hvd гарантированно работает. (Обратите внимание, что из-за заполнения INT_MAX может быть намного меньше, чем UINT_MAX / 2 ... Но благодаря тому, как работают приведения со знаком-> без знака, этот ответ справляется с этим нормально.)

C ++ 03 / C ++ 98 сложнее. Он использует ту же формулировку, чтобы унаследовать <climits>от "Standard C", но теперь "Standard C" означает C89 / C90.

Все они - C ++ 98, C ++ 03, C89 / C90 - имеют формулировку, которую я даю в своем вопросе, но также включают это (C ++ 03 раздел 3.9.1 параграф 7):

Представления целочисленных типов должны определять значения с использованием чистой двоичной системы счисления. (44) [ Пример : этот международный стандарт разрешает представления значений с дополнением до 2, дополнением до единицы и представления величины со знаком для целочисленных типов.]

В сноске (44) определяется «чисто двоичная система счисления»:

Позиционное представление для целых чисел, использующее двоичные цифры 0 и 1, в котором значения, представленные последовательными битами, являются аддитивными, начинаются с 1 и умножаются на последовательную интегральную степень 2, за исключением, возможно, бита с самой высокой позицией.

Что интересно в этой формулировке, так это то, что она противоречит сама себе, потому что определение «чистой двоичной системы счисления» не допускает представления знака / величины! Это позволяет старшему биту иметь, скажем, значение -2 ^n-1 (дополнение до двух) или - (2 ^n-1 -1) (дополнение до единиц). Но нет значения для старшего бита, который приводит к знаку / величине.

В любом случае моя «гипотетическая реализация» не может считаться «чистой двоичной» согласно этому определению, поэтому она исключена.

Однако тот факт, что старший бит является особым, означает, что мы можем представить, что он вносит какое-либо значение вообще: небольшое положительное значение, огромное положительное значение, небольшое отрицательное значение или огромное отрицательное значение. (Если знаковый бит может способствовать - (2 ^n-1 -1), почему бы не - (2 ^n-1 -2)? И т. Д.)

Итак, давайте представим целочисленное представление со знаком, которое присваивает дурацкое значение биту «знака».

Небольшое положительное значение для знакового бита приведет к положительному диапазону int(возможно, до unsigned), и код hvd справляется с этим отлично.

Огромное положительное значение знакового бита приведет к тому, intчто максимальное значение будет больше, чем unsigned, что запрещено.

Огромное отрицательное значение для знакового бита приведет к intпредставлению несмежного диапазона значений, и другие формулировки в спецификации это исключают.

Наконец, как насчет знакового бита, вносящего небольшую отрицательную величину? Может ли 1 в «знаковом бите» вносить, скажем, -37 в значение int? Итак INT_MAX бы (скажем) 2 ³¹ -1 и INT_MIN бы -37?

Это приведет к тому, что некоторые числа будут иметь два представления ... Но дополнение до единиц дает два представления до нуля, и это разрешено в соответствии с «Примером». В спецификации нигде не говорится, что ноль - единственное целое число, которое может иметь два представления. Так что я думаю, что эта новая гипотеза допускается спецификацией.

В самом деле, любое отрицательное значение от -1 до -INT_MAX-1кажется допустимым в качестве значения для «знакового бита», но не меньше (чтобы диапазон не был непрерывным). Другими словами, это INT_MINможет быть что угодно от -INT_MAX-1-1.

Теперь угадайте, что? Для второго приведения в коде hvd, чтобы избежать поведения, определяемого реализацией, нам просто нужно x - (unsigned)INT_MINменьше или равно INT_MAX. Мы только что показали INT_MINэто как минимум -INT_MAX-1. Очевидно, xсамое большее UINT_MAX. Преобразование отрицательного числа в число без знака аналогично сложению UINT_MAX+1. Положил все это вместе:

x - (unsigned)INT_MIN <= INT_MAX

если и только если

UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX
-INT_MIN-1 <= INT_MAX
-INT_MIN <= INT_MAX+1
INT_MIN >= -INT_MAX-1

Это последнее, что мы только что показали, поэтому даже в этом извращенном случае код действительно работает.

На этом все возможности исчерпаны, и это чрезвычайно академическое упражнение заканчивается.

Итог: в C89 / C90 существует серьезное недоопределенное поведение для целых чисел со знаком, которые унаследованы C ++ 98 / C ++ 03. Это исправлено в C99, а C ++ 11 косвенно наследует исправление путем включения <limits.h>из C99. Но даже C ++ 11 сохраняет противоречивую формулировку «чистого двоичного представления» ...

Этот код полагается только на поведение, предписанное спецификацией, поэтому требование (а) легко выполняется:

int unsigned_to_signed(unsigned n)
{
  int result = INT_MAX;

  if (n > INT_MAX && n < INT_MIN)
    throw runtime_error("no signed int for this number");

  for (unsigned i = INT_MAX; i != n; --i)
    --result;

  return result;
}

С требованием (б) все не так просто. Это компилируется в no-op с gcc 4.6.3 (-Os, -O2, -O3) и с clang 3.0 (-Os, -O, -O2, -O3). Intel 12.1.0 отказывается оптимизировать это. И у меня нет информации о Visual C.

Исходный ответ решил проблему только для unsigned=> int. Что, если мы хотим решить общую проблему «некоторого беззнакового типа» для соответствующего ему знакового типа? Более того, исходный ответ превосходно цитировал разделы стандарта и анализировал некоторые критические случаи, но на самом деле он не помог мне понять, почему он работает, поэтому этот ответ попытается дать прочную концептуальную основу. Этот ответ попытается объяснить «почему» и использовать современные функции C ++, чтобы попытаться упростить код.

C ++ 20 ответ

Проблема значительно упростилась с P0907: Целые числа со знаком - это два дополнения и окончательной формулировкой P1236, которая была признана стандартом C ++ 20. Теперь ответ предельно прост:

template<std::unsigned_integral T>
constexpr auto cast_to_signed_integer(T const value) {
    return static_cast<std::make_signed_t<T>>(value);
}

Вот и все. Приведение static_cast(или приведение в стиле C) наконец-то гарантированно сделает то, что вам нужно для ответа на этот вопрос, и многие программисты думали, что это всегда так.

C ++ 17 ответ

В C ++ 17 все намного сложнее. Нам нужно иметь дело с тремя возможными целочисленными представлениями (дополнение до двух, дополнение до единиц и величина знака). Даже в том случае, когда мы знаем, что это должно быть два дополнения, поскольку мы проверили диапазон возможных значений, преобразование значения вне диапазона целого числа со знаком в это целое число со знаком все равно дает нам результат, определяемый реализацией. Мы должны использовать уловки, как мы видели в других ответах.

Во-первых, вот код общего решения проблемы:

template<typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
constexpr auto cast_to_signed_integer(T const value) {
    using result = std::make_signed_t<T>;
    using result_limits = std::numeric_limits<result>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<T>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<result>(value);
    } else {
        using promoted_unsigned = std::conditional_t<sizeof(T) <= sizeof(unsigned), unsigned, T>;
        using promoted_signed = std::make_signed_t<promoted_unsigned>;
        constexpr auto shift_by_window = [](auto x) {
            // static_cast to avoid conversion warning
            return x - static_cast<decltype(x)>(result_limits::max()) - 1;
        };
        return static_cast<result>(
            shift_by_window( // shift values from common range to negative range
                static_cast<promoted_signed>(
                    shift_by_window( // shift large values into common range
                        static_cast<promoted_unsigned>(value) // cast to avoid promotion to int
                    )
                )
            )
        );
    }
}

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

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

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

Концептуальная основа: числовая линия

Во-первых, что это за windowконцепция? Рассмотрим следующую числовую строку:

   |   signed   |
<.........................>
          |  unsigned  |

Оказывается, что для двух дополнительных целых чисел вы можете разделить подмножество числовой строки, которое может быть достигнуто любым типом, на три категории одинакового размера:

- => signed only
= => both
+ => unsigned only

<..-------=======+++++++..>

В этом легко убедиться, рассмотрев представление. Целое число без знака начинается с 0и использует все биты для увеличения значения в степени 2. Целое число со знаком точно такое же для всех битов, за исключением знакового бита, который стоит -(2^position)вместо 2^position. Это означает, что для всех n - 1битов они представляют одинаковые значения. Затем целые числа без знака имеют еще один нормальный бит, который удваивает общее количество значений (другими словами, существует столько же значений с этим битом, сколько и без него). Та же логика применяется для целых чисел со знаком, за исключением того, что все значения с этим набором битов отрицательны.

Два других допустимых целочисленных представления, дополнение до единицы и величина знака, имеют все те же значения, что и два дополнительных целых числа, за исключением одного: самого отрицательного значения. C ++ определяет все, что касается целочисленных типов, за исключением reinterpret_cast(и C ++ 20 std::bit_cast), с точки зрения диапазона представляемых значений, а не с точки зрения битового представления. Это означает, что наш анализ будет справедлив для каждого из этих трех представлений до тех пор, пока мы никогда не попытаемся создать представление ловушки. Значение без знака, которое будет отображаться на это отсутствующее значение, является довольно неудачным: оно находится прямо в середине значений без знака. К счастью, наше первое условие проверяет (во время компиляции), существует ли такое представление, а затем обрабатывает его специально с проверкой во время выполнения.

Первое условие обрабатывает случай, когда мы находимся в =разделе, что означает, что мы находимся в перекрывающейся области, где значения в одном могут быть представлены в другом без изменений. shift_by_windowФункции в коде перемещают все значения вниз по размеру каждым из этих сегментов (мы должны вычесть максимальное значение , а затем вычесть 1 , чтобы избежать арифметических проблем переполнения). Если мы находимся за пределами этого региона (мы находимся в этом регионе), чтобы снова получить уникальное отображение.+ регионе), нам нужно перепрыгнуть вниз на один размер окна. Это помещает нас в перекрывающийся диапазон, что означает, что мы можем безопасно преобразовать беззнаковый в подписанный, потому что нет изменения значения. Однако мы еще не закончили, потому что мы сопоставили два значения без знака каждому значению со знаком. Следовательно, нам нужно перейти к следующему окну (-

Теперь, дает ли это нам результат, совпадающий с модом UINT_MAX + 1, как запрошено в вопросе? UINT_MAX + 1эквивалентно 2^n, где n- количество бит в представлении значения. Значение, которое мы используем для размера нашего окна, равно 2^(n - 1)(последний индекс в последовательности значений на единицу меньше размера). Мы вычитаем это значение дважды, что означает, что мы вычитаем значение, 2 * 2^(n - 1)равное 2^n. Сложение и вычитание xне xвыполняются в арифметическом режиме , поэтому мы не повлияли на исходное значение мода 2^n.

Правильная обработка целочисленных рекламных акций

Поскольку это общая функция, а не только intи unsigned, мы также должны учитывать общие правила продвижения. Есть два, возможно, интересных случая: один shortменьше, intа другой shortтого же размера, что и int.

Пример: shortменьше чемint

Если shortменьше, чем int(распространено на современных платформах), мы также знаем, что оно unsigned shortможет поместиться в int, что означает, что любые операции с ним действительно будут происходить int, поэтому мы явно приводим его к продвинутому типу, чтобы этого избежать. Наше последнее утверждение довольно абстрактно, и его будет легче понять, если мы подставим реальные значения. Для нашего первого интересного случая, без потери общности, давайте рассмотрим 16-битный shortи 17-битный int(который все еще разрешен в соответствии с новыми правилами и будет просто означать, что по крайней мере один из этих двух целочисленных типов имеет некоторые биты заполнения ):

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int17_t>(
            shift_by_window(
                static_cast<uint17_t>(value)
            )
        )
    )
);

Решение для максимально возможного 16-битного беззнакового значения

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return int16_t(
    shift_by_window(
        int17_t(
            shift_by_window(
                uint17_t(65535)
            )
        )
    )
);

Упрощается до

return int16_t(
    int17_t(
        uint17_t(65535) - uint17_t(32767) - 1
    ) -
    int17_t(32767) -
    1
);

Упрощается до

return int16_t(
    int17_t(uint17_t(32767)) -
    int17_t(32767) -
    1
);

Упрощается до

return int16_t(
    int17_t(32767) -
    int17_t(32767) -
    1
);

Упрощается до

return int16_t(-1);

Вставляем как можно больше неподписанных и возвращаемся -1, удачи!

Пример: shortтакой же размер, какint

Если shortон того же размера, что и int(редко на современных платформах), общие правила продвижения немного отличаются. В этом случае shortпродвигает до intи unsigned shortпродвигает до unsigned. К счастью, мы явно приводим каждый результат к тому типу, в котором мы хотим производить вычисления, поэтому в итоге мы не получаем проблемных рекламных акций. Не умаляя общности, рассмотрим 16-битный shortи 16-битный int:

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int16_t>(
            shift_by_window(
                static_cast<uint16_t>(value)
            )
        )
    )
);

Решение для максимально возможного 16-битного беззнакового значения

auto x = int16_t(
    uint16_t(65535) - uint16_t(32767) - 1
);
return int16_t(
    x - int16_t(32767) - 1
);

Упрощается до

return int16_t(
    int16_t(32767) - int16_t(32767) - 1
);

Упрощается до

return int16_t(-1);

Вставляем как можно больше неподписанных и возвращаемся -1, удачи!

Что делать , если я просто заботиться о intи unsignedи не заботятся о предупреждениях, как оригинальный вопрос?

constexpr int cast_to_signed_integer(unsigned const value) {
    using result_limits = std::numeric_limits<int>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<unsigned>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<int>(value);
    } else {
        constexpr int window = result_limits::min();
        return static_cast<int>(value + window) + window;
    }
}

Смотрите вживую

https://godbolt.org/z/74hY81

Здесь мы видим, что clang, gcc и icc не генерируют код для castи cast_to_signed_integer_basicв -O2и -O3, а MSVC не генерирует код в /O2, поэтому решение является оптимальным.

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

int unsigned_to_signed(unsigned n) {
  if (n > INT_MAX) {
    if (n <= UINT_MAX + INT_MIN) {
      throw "no result";
    }
    return static_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1);
  } else {
    return static_cast<int>(n);
  }
}

Компилируется с gcc 4.7.2for x86_64-linux( g++ -O -S test.cpp) в

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret

Если xэто наш вклад ...

Если x > INT_MAXмы хотим , чтобы найти константу kтакую , что 0< x - k*INT_MAX< INT_MAX.

Это просто - unsigned int k = x / INT_MAX;. Тогда пустьunsigned int x2 = x - k*INT_MAX;

Теперь мы можем бросить x2в intбезопасности. Позволятьint x3 = static_cast<int>(x2);

Теперь мы хотим , чтобы вычитать что - то вроде UINT_MAX - k * INT_MAX + 1с x3, если k > 0.

Теперь, в системе с дополнением до 2-х секунд, если x > INT_MAXэто работает:

unsigned int k = x / INT_MAX;
x -= k*INT_MAX;
int r = int(x);
r += k*INT_MAX;
r -= UINT_MAX+1;

Обратите внимание, что UINT_MAX+1в C ++ гарантировано нулевое значение, преобразование в int было пустым, и мы вычлиk*INT_MAX затем добавляли его обратно для «того же значения». Так что приемлемый оптимизатор должен уметь стереть все эти дурацкие глупости!

Остается проблема x > INT_MAXили нет. Итак, мы создаем 2 ветки, одну с x > INT_MAX, а другую без. Тот, у кого нет, выполняет прямое приведение, которое компилятор оптимизирует до нуля. Тот, у которого есть ..., после того, как оптимизатор завершил работу, не отвечает. Интеллектуальный оптимизатор реализует обе ветви для одного и того же и отбрасывает ветку.

Проблемы: если UINT_MAXон действительно большой по сравнению с INT_MAX, вышеуказанное может не работать. Я предполагаю это k*INT_MAX <= UINT_MAX+1неявно.

Вероятно, мы могли бы атаковать это с помощью некоторых перечислений, например:

enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };

которые работают до 2 и 1 в системе с двумя дополнениями, как я полагаю (гарантировано ли нам, что эта математика работает? Это сложно ...), и делают логику, основанную на них, которая легко оптимизируется для систем с дополнением без двух ...

Это также открывает случай исключения. Это возможно только в том случае, если UINT_MAX намного больше, чем (INT_MIN-INT_MAX), поэтому вы можете поместить свой код исключения в блок if, каким-то образом задающий именно этот вопрос, и это не замедлит вас в традиционной системе.

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

std::numeric_limits<int>::is_moduloпостоянная времени компиляции. так что вы можете использовать его для специализации шаблона. проблема решена, по крайней мере, если компилятор подыгрывает встраиванию.

#include <limits>
#include <stdexcept>
#include <string>

#ifdef TESTING_SF
    bool const testing_sf = true;
#else
    bool const testing_sf = false;
#endif

// C++ "extensions"
namespace cppx {
    using std::runtime_error;
    using std::string;

    inline bool hopefully( bool const c ) { return c; }
    inline bool throw_x( string const& s ) { throw runtime_error( s ); }

}  // namespace cppx

// C++ "portability perversions"
namespace cppp {
    using cppx::hopefully;
    using cppx::throw_x;
    using std::numeric_limits;

    namespace detail {
        template< bool isTwosComplement >
        int signed_from( unsigned const n )
        {
            if( n <= unsigned( numeric_limits<int>::max() ) )
            {
                return static_cast<int>( n );
            }

            unsigned const u_max = unsigned( -1 );
            unsigned const u_half = u_max/2 + 1;

            if( n == u_half )
            {
                throw_x( "signed_from: unsupported value (negative max)" );
            }

            int const i_quarter = static_cast<int>( u_half/2 );
            int const int_n1 = static_cast<int>( n - u_half );
            int const int_n2 = int_n1 - i_quarter;
            int const int_n3 = int_n2 - i_quarter;

            hopefully( n == static_cast<unsigned>( int_n3 ) )
                || throw_x( "signed_from: range error" );

            return int_n3;
        }

        template<>
        inline int signed_from<true>( unsigned const n )
        {
            return static_cast<int>( n );
        }
    }    // namespace detail

    inline int signed_from( unsigned const n )
    {
        bool const is_modulo = numeric_limits< int >::is_modulo;
        return detail::signed_from< is_modulo && !testing_sf >( n );
    }
}    // namespace cppp

#include <iostream>
using namespace std;
int main()
{
    int const x = cppp::signed_from( -42u );
    wcout << x << endl;
}

Я думаю, что тип int составляет не менее двух байтов, поэтому INT_MIN и INT_MAX могут меняться на разных платформах.

Основные типы

≤climits≥ заголовок

Мои деньги идут на использование memcpy. Любой достойный компилятор знает, как его оптимизировать:

#include <stdio.h>
#include <memory.h>
#include <limits.h>

static inline int unsigned_to_signed(unsigned n)
{
    int result;
    memcpy( &result, &n, sizeof(result));
    return result;
}

int main(int argc, const char * argv[])
{
    unsigned int x = UINT_MAX - 1;
    int xx = unsigned_to_signed(x);
    return xx;
}

Для меня (Xcode 8.3.2, Apple LLVM 8.1, -O3), который производит:

_main:                                  ## @main
Lfunc_begin0:
    .loc    1 21 0                  ## /Users/Someone/main.c:21:0
    .cfi_startproc
## BB#0:
    pushq    %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    ##DEBUG_VALUE: main:argc <- %EDI
    ##DEBUG_VALUE: main:argv <- %RSI
Ltmp3:
    ##DEBUG_VALUE: main:x <- 2147483646
    ##DEBUG_VALUE: main:xx <- 2147483646
    .loc    1 24 5 prologue_end     ## /Users/Someone/main.c:24:5
    movl    $-2, %eax
    popq    %rbp
    retq
Ltmp4:
Lfunc_end0:
    .cfi_endproc