Каков стандартный способ конвертирования подписанного целочисленного значения в сортируемый, неподписанный в С++?

У меня есть прецедент, когда мне нужно преобразовать знаковые значения в unsigned, чтобы значения сортировались. Мне нужно это для char, short, int, long и long long

С помощью сортировки я имею в виду, что для signed типа X, если (a < b), то преобразование в unsigned converted(a) < converted(b). Обратите внимание, что во многих случаях преобразование из отрицательного значения signed непосредственно в значение unsigned сделает значение больше, чем 0, и разрывает это ограничение (две реализации дополнения)

Простейшей идеей для char является:

unsigned char convert(char x)
{
       return (unsigned char)(x ^ 0x80);  // flip sign to make it sortable
}

Но это кажется undefined behavior.

В то время как можно было бы преобразовать в более крупный тип, добавить значения типа MIN и преобразовать в тип unsigned, я не уверен, что это более совместимо и не будет работать с long long

Как это можно сделать без каких-либо undefined behavior для всех типов?

Кажется безопасным преобразование с помощью memcpy, но неясно, как поддерживать порядок сортировки с соблюдением.

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

Ответ 1

Это невозможно, если вы хотите оставаться полностью переносимым.

Диапазон unsigned int определяется только по крайней мере для покрытия неотрицательных значений int. Стандарт допускает реализацию, где UINT_MAX == INT_MAX. То же самое относится ко всем другим целым типам нефиксированной ширины.

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

Чтобы процитировать N4140 (примерно С++ 14):

3.9.1 Основные типы [basic.fundamental]

1 [...] Для типов узких символов в представлении значений участвуют все биты представления объекта. Для беззнаковых узких типов символов все возможные битовые шаблоны представления значений представляют числа. Эти требования не подходят для других типов. [...]

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

Это гарантирует, что у вас нет проблемы для unsigned char. Нет возможности для unsigned char иметь любые биты заполнения. Для unsigned char было бы бессмысленно иметь биты заполнения: данный unsigned char c;, как бы вы получили доступ к этим битам заполнения? reinterpret_cast<unsigned char &>(c)? Это явно дает вам c. Единственное, что похоже на биты дополнений, которое возможно для unsigned char, - это то, что полностью прозрачно для программы, например, когда используется память ECC.

Для всего другого целочисленного типа нефиксированной ширины, от short до long long, стандартное значение "поддиапазона" допускает равный диапазон.

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

Ответ 2

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

Можно использовать двухбитовые типы:

          00    01 10  11  Order for unsigned               0     1  2  3
10  11    00    01         Order for 2s complement -2 -1    0     1
    11 (10  00) 01         Order for sign-magnitude   -1 (-0 +0)  1
    10 (11  00) 01         Order for 1s-complement    -1 (-0 +0)  1

То, что вы хотите сделать, - это преобразовать в unsigned (который всегда определяется как сохранение значения, с оберткой), а затем добавить смещение, поэтому наиболее отрицательное число становится 0:

int x = whatever;
unsigned r = (unsigned)x - (unsigned)INT_MIN;

Будьте осторожны: Подписанное переполнение не определено, поэтому мы избегаем подписанных типов.

Конечно, это не помогает, если тип unsigned имеет меньшее значение, чем подписанное, что разрешено вообще, хотя и не для char.
И вам нужно проявлять особую осторожность, если вы хотите сохранить отрицательный 0 как отрицательный.

Ответ 3

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

a) их относительные различия не изменяются и

b) все отрицательные значения превращаются в неотрицательные значения.

Добавление согласованной суммы - единственный способ сделать это. Если все значения, которые вы сортируете, первоначально имеют один и тот же тип подписанного типа T, тогда сумма, добавляемая для обеспечения того, чтобы любое отрицательное значение становилось неотрицательным, должно быть "-numeric_limits:: min()" или, другими словами, вы должны вычесть минимальное значение знака, отрицательное.

Если вы вводите разные типы в один и тот же сорт (например, сортировка значений char вместе с short, int, long и т.д.), вы можете сделать первый шаг преобразованием в наибольшую подписанную, с которым вы справитесь. Нет никакой потери информации от меньшего подписанного типа до более крупного подписанного типа.

Чтобы избежать проблем с переполнением, я бы предложил сделать сдвиг (т.е. вычесть минимум) условно.

if (значение < 0)

конвертировать, сначала вычитая минимум (делая неотрицательный), а затем преобразовать в неподписанный тип (который теперь полностью безопасен)

еще

сначала преобразовать уже неотрицательное значение в неподписанный тип (полностью безопасно), а затем добавить ту же настройку, что и положительное значение, то есть добавить numeric_limits:: max() + 1

T для обоих - это оригинал, подписанный T. Выражение "numeric_limits:: max() + 1" можно было вычислить и преобразовать в новый тип назначения один раз, а затем использовать как константу в типе newT.

Ответ 4

Я бы вычитал numeric_limits<T>::min() из каждого значения. Это сохраняет свойство упорядочения, которое вы хотите, и если базовое представление представляет собой 2 дополнения (т.е. Единственное нормальное представление и то, что на практике используется каждым компьютером, не использующим музей), будет делать то, что вы ожидаете, в том числе для граничные случаи, когда входное значение равно наибольшему отрицательному или наиболее положительному представляемому целому числу - при условии, что компилятор использует инструкцию SUB, а не инструкцию ADD (так как положительное значение -numeric_limits<T>::min() слишком велико для представления).

Является ли этот стандарт совместимым? Без понятия. Мое предположение: Вероятно, нет. Не стесняйтесь редактировать, если знаете.

Ответ 5

Формула x-(unsigned)INT_MIN даст подходящий рейтинг на всех машинах, где UINT_MAX > INT_MAX. Для любой пары знаковых целых чисел x и y, где x >= y, (без знака) x- (без знака) y будет равен числовому значению x-y; поэтому, если y INT_MIN, тогда x >= y для всех x, и указанная выше формула сообщит сумму, на которую x больше INT_MIN, что, конечно, считается таким же, как x.