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

Question

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

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

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

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

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

Что касается странных машин... Если нет подписанного 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
• Вызывать только стандартное поведение
• Скомпилируйте в no-op на типичной машине с двумя комплементами с оптимизирующим компилятором

[Обновить]

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

Рассмотрим гипотетическую реализацию 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 значение конгруэнтное (мод UINT_MAX+1) каждому unsigned значение. Так что мой вопрос будет четко определен.

Я утверждаю, что эта гипотетическая реализация 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++, доказывающий, что я ошибаюсь.

Answer 1

Расширяя ответ user71404:

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>,

...

Содержимое совпадает с заголовком библиотеки Standard 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> от "Стандарт С", но теперь "Стандарт С" означает С89/ С90.

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

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

Сноска (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 сохраняется противоречивая формулировка "чисто двоичное представление"...

Answer 2

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

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.

Answer 3

Исходный ответ решил проблему только для 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 unsigned_t = std::conditional_t<sizeof(T) <= sizeof(unsigned), unsigned, T>;
    using signed_t = std::make_signed_t<unsigned_t>;
    using result_t = std::make_signed_t<T>;
    using result_limits = std::numeric_limits<result_t>;
    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_t>(value);
    } else {
        constexpr auto window = static_cast<signed_t>(result_limits::min());
        return static_cast<result_t>( // cast to the type we want the result in
            static_cast<signed_t>( // cast back to signed or we end up with our original value
                static_cast<T>( // cast to unsigned to force modular reduction
                    static_cast<unsigned_t>(value) + // cast to avoid promotion to int
                    static_cast<unsigned_t>(window) // shift values to overlapping range, cast to silence warning
                )
            ) + window // shift values to negative range
        );
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

Теперь, дает ли это нам результат, совпадающий с модом 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 window = static_cast<int17_t>(result_limits::min());
return static_cast<int16_t>(
    static_cast<int17_t>(
        static_cast<uint16_t>(
            static_cast<uint17_t>(value) +
            static_cast<uint17_t>(window)
        )
    ) + window
);

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

constexpr auto window = int17_t(-32768);
return int16_t(
    int17_t(
        uint16_t(
            uint17_t(65535) +
            uint17_t(window)
        )
    ) + window
);

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

return int16_t(
    int17_t(
        uint16_t(
            uint17_t(65535) +
            uint17_t(32768)
        )
    ) +
    int17_t(-32768)
);

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

return int16_t(
    int17_t(
        uint16_t(
            uint17_t(98303)
        )
    ) +
    int17_t(-32768)
);

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

return int16_t(
    int17_t(
        uint16_t(32767)
    ) +
    int17_t(-32768)
);

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

return int16_t(-1);

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

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

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

constexpr auto window = static_cast<int16_t>(result_limits::min());
return static_cast<int16_t>(
    static_cast<int16_t>(
        static_cast<uint16_t>(
            static_cast<uint16_t>(value) +
            static_cast<uint16_t>(window)
        )
    ) + window
);

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

return int16_t(
    int16_t(
        uint16_t(
            uint16_t(65535) +
            uint16_t(32768)
        )
    ) +
    int16_t(-32768)
);

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

return int16_t(
    int16_t(32767) + int16_t(-32768)
);

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

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/AmLazZ

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

Answer 4

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

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.2 за x86_64-linux (g++ -O -S test.cpp) чтобы

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret

Answer 5

Если 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,

Теперь в системе дополнения 2s, так долго, как 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и один без. Тот, у кого нет, делает прямое приведение, которое компилятор оптимизирует до нуля. Тот, который... делает noop после завершения работы оптимизатора. Интеллектуальный оптимизатор понимает обе ветви на одно и то же и отбрасывает ветку.

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

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

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

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

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

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

Answer 6

Мои деньги на использование 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

Answer 7

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 (известно, что существует только одна, а именно, архаически сконфигурированные версии Unisys Clearpath). Для простоты это сделано, не поддерживая значение -2 ^{n -1,} где n - число int биты значений, на такой машине (т.е. на Clearpath). на практике это значение также не будет поддерживаться машиной (т. е. со знаком и величиной или представлением дополнения 1).

Answer 8

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

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

≤climits≥ header

Answer 9

Это полностью соответствует стандартам и будет компилироваться в no-op на MSVC/gcc.

int unsigned_to_signed(unsigned int n)
{
    union UltimateCast
    {
        unsigned int In;
        int Out;
    } cast;

    cast.In = n;

    return cast.Out;
}

Для кода вызова, как:

volatile unsigned int i = 32167;

int main()
{
    return unsigned_to_signed( i );
}

У нас будет вывод этой сборки (g++ -O3 -S):

__Z18unsigned_to_signedj:
    movl    4(%esp), %eax
    ret
_main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    call    ___main
    movl    _i, %eax
    leave
    ret
    .globl  _i
    .data
    .align 4
_i:
    .long   32167

И декларируя unsigned_to_signed() как inline выходы:

_main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    call    ___main
    movl    _i, %eax
    leave
    ret
    .globl  _i
    .data
    .align 4
_i:
    .long   32167

Это довольно аккуратный код.