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

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

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

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

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

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

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

ОК, вторая попытка:

 int unsigned_to_signed(unsigned n) { int int_n = static_cast(n); if (n == static_cast(int_n)) return int_n; // else do something long and complicated } 

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

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

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

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

Напомню, я хочу:

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

[Обновить]

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

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

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

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

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

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

Кстати, обратите внимание, что std::numeric_limits::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 spec. И нет ничего, что бы означало единичный знак или что-то в этом роде. Все, что он говорит, это то, что неотрицательные целые числа со знаком должны быть поддиапазоном соответствующего без знака.

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

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

 int f(unsigned x) { if (x <= INT_MAX) return static_cast(x); if (x >= INT_MIN) return static_cast(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 32 + 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 (на этой платформе).

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

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

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

В таблице 31 описывается заголовок .

...

Содержимое совпадает с заголовком библиотеки Standard C .

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

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

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

Все из них - C ++ 98, C ++ 03, C89 / C90 - имеют формулировку, которую я даю в моем вопросе, но также include это (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 31 -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 . Отбрасывание отрицательного числа в unsigned совпадает с добавлением 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 косвенно наследует исправление путем включения из 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.

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

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

Компилирует с gcc 4.7.2 для 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(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 было 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, я полагаю (мы гарантируем, что эта математика будет работать? Это сложно ...), и на основе этих логических соображений легко оптимизируется система дополнений, отличных от 2-х ...

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

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

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

 #include  #include  #include  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 

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

 #include  #include  #include  #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::max() ) ) { return static_cast( 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( u_half/2 ); int const int_n1 = static_cast( n - u_half ); int const int_n2 = int_n1 - i_quarter; int const int_n3 = int_n2 - i_quarter; hopefully( n == static_cast( int_n3 ) ) || throw_x( "signed_from: range error" ); return int_n3; } template<> inline int signed_from( unsigned const n ) { return static_cast( 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  using namespace std; int main() { int const x = cppp::signed_from( -42u ); wcout << x << endl; } 

EDIT : Исправлен код, чтобы избежать возможной ловушки на немодульных машинах (только один из них, как известно, существует, а именно архаически настроенные версии Unisys Clearpath). Для простоты это делается, не поддерживая значение -2 n -1, где n - количество битов значения int , на такой машине (то есть на Clearpath). на практике это значение не будет поддерживаться машиной либо (т. е. с представлением знака и величины или 1).

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

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

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

Это совершенно стандартно совместимо и будет компилироваться в 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 ); } 

У нас будет этот assembly (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 

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

  • Доступ к атрибутам на литералах работает на всех типах, но не `int`; Зачем?
  • Чистые виртуальные функции могут не иметь встроенного определения. Зачем?
  • Удаленный конструктор по умолчанию. Объекты все еще могут быть созданы ... иногда
  • Когда это действительно для доступа к указателю на «мертвый» объект?
  • int a = {1,2,}; Разрешена странная запятая. Любая конкретная причина?
  • При использовании заголовков C в C ++ следует ли использовать функции из std :: или глобального пространства имен?
  • «Создание» объекта с возможностью копирования с возможностью memcpy
  • Возьмите адрес элемента массива «один конец прошлого» через индекс: легальный по стандарту C ++ или нет?
  • Имеет ли printf ("% x", 1) неопределенное поведение?
  • Давайте будем гением компьютера.