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

Ответ 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.

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

[Обновление от опроса (Nemo), в котором мы обсудим ниже]

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

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

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

...

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

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

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

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

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

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

Сноска (44) определяет "чистую двоичную систему нумерации":

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

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

Во всяком случае, моя "гипотетическая реализация" не квалифицируется как "чистая двоичная" в соответствии с этим определением, поэтому она исключается.

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

Итак, представьте себе целочисленное представление со знаком, которое присваивает пустое значение бит "sign".

Небольшое положительное значение для знакового бита приведет к положительному диапазону для 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, которые были унаследованы С++ 98/С++ 03. Он исправлен в C99, а С++ 11 косвенно наследует исправление путем включения <limits.h> из C99. Но даже С++ 11 сохраняет само противоречивую формулировку "чистого двоичного представления"...

Ответ 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.

Ответ 3

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

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

Ответ 4

Если 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 равен нулю в С++, преобразование в int было noop, и мы вычитали k*INT_MAX, а затем добавили его обратно к "тому же значению". Таким образом, приемлемый оптимизатор должен иметь возможность стереть все эти глупости!

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

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

Ответ 5

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

#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;
}

Ответ 6

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

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

& le; climits & ge; Заголовок

Ответ 7

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

Ответ 8

Эта проблема значительно упростилась благодаря P0907: подписанные целые числа являются дополнением к двойке и окончательной формулировкой P1236, которая была утверждена в стандарте С++ 20.

Однако оригинальный ответ решил проблему только для unsigned => int. Что, если мы хотим решить общую проблему "некоторого типа без знака" с соответствующим типом со знаком? Кроме того, оригинальный ответ был превосходным при цитировании разделов стандарта и анализе некоторых ключевых случаев, но он не очень помог мне понять, почему он работает, поэтому этот ответ попытается дать прочную концептуальную основу.

Ответ с++ 20

template<std::unsigned_integral 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 (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 они представляют одинаковые значения. Затем целые числа без знака имеют еще один нормальный бит, который удваивает общее количество значений (другими словами, с таким битом установлено столько же значений, сколько и без него). Та же логика действует для целых чисел со знаком, за исключением того, что все значения с этим установленным битом отрицательны.

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

Теперь, дает ли это нам конгруэнтный мод результата 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 (который все еще разрешен в соответствии с новыми правилами и должен иметь как минимум 7 битов заполнения). ):

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 (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/zc3R35

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

Ответ 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

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