Программное определение максимального значения целочисленного типа со знаком

Question

Этот связанный вопрос касается определения максимального значения типа со знаком во время компиляции:

C вопрос: минимальные и максимальные значения off_t (и других целочисленных типов со знаком)

Однако с тех пор я понял, что определение максимального значения типа со знаком (например, time_t или off_t) в время выполнения представляется очень сложной задачей.

Ближайшее решение, о котором я могу подумать, это:

uintmax_t x = (uintmax_t)1<<CHAR_BIT*sizeof(type)-2;
while ((type)x<=0) x>>=1;

Это позволяет избежать циклов, если type не имеет битов заполнения, но если type имеет биты заполнения, приведение вызывает поведение, определяемое реализацией, которое может быть сигналом или бессмысленным преобразованием, определяемым реализацией (например зачистка знака).

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

Answer 1

Давайте сначала посмотрим, как C определяет «целочисленные типы». Взято из ИСО / МЭК 9899 , §6.2.6.2:

6.2.6.2 Целочисленные типы
1
Для целочисленных типов без знака, кроме знака без знака, биты объекта представление должно быть разделено на две группы: биты значения и биты заполнения (там необходимо не будь ни одного из последних). Если имеется N битов значения, каждый бит должен представлять разные мощность 2 между 1 и 2N − 1, так что объекты этого типа должны быть способны представление значений от 0 до 2N - 1 с использованием чисто двоичного представления; это должно быть известный как представление значения. Значения любых битов заполнения не определены.44)
2
Для целочисленных типов со знаком биты представления объекта делятся на три группы: биты значения, биты заполнения и бит знака. Там не должно быть никаких битов заполнения; должен быть ровно один знаковый бит. Каждый бит, который является битом значения, должен иметь то же значение, что и тот же бит в представлении объекта соответствующего типа без знака (если имеется M битов значения в типе со знаком и N в типе без знака, то M ≤ N). Если знак бит ноль, это не должно влиять на результирующее значение. Если знаковый бит равен единице, значение должно быть изменяется одним из следующих способов:

- соответствующее значение со знаковым битом 0 обнуляется (знак и величина);
- знаковый бит имеет значение - (2N) (дополнение до двух);
- знаковый бит имеет значение - (2N - 1) (дополнение).

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

Следовательно, мы можем заключить следующее:

• ~(int)0 может быть представлением ловушки, то есть установка всех битов является плохой идеей
• В int могут быть биты заполнения, которые не влияют на его значение
• Порядок битов, фактически представляющих степени двух, не определен; так же и положение знакового бита, если он существует.

Хорошая новость заключается в том, что:

• есть только один знаковый бит
• есть только один бит, который представляет значение 1

Имея это в виду, есть простая техника, чтобы найти максимальное значение int. Найдите знаковый бит, затем установите его в 0 и установите все остальные биты в 1.

Как мы находим бит знака? Рассмотрим int n = 1;, который строго положителен и гарантирует, что только один бит и, возможно, некоторые биты заполнения будут установлены в 1. Затем для всех других битов i, если i==0 имеет значение true, установите его в 1 и посмотрите, результирующее значение отрицательно. Если это не так, верните его обратно в 0. В противном случае мы нашли бит знака.

Теперь, когда мы знаем положение бит знака, мы берем наш int n, устанавливаем бит знака на ноль, а все остальные биты равны 1, и tadaa, мы получаем максимально возможное значение int.

Определение минимума int немного сложнее и оставлено читателю в качестве упражнения.

Обратите внимание, что стандарту С юмористически не требуется, чтобы два разных int вели себя одинаково. Если я не ошибаюсь, могут быть два различных объекта int, которые имеют, например, их соответствующие знаковые биты в разных позициях.

РЕДАКТИРОВАТЬ: обсуждая этот подход с R .. (см. Комментарии ниже), я убедился, что он имеет недостатки в нескольких отношениях и, в более общем плане, что решения вообще не существует. Я не вижу способа исправить это сообщение (кроме как удалить его), поэтому я оставил его без изменений для комментариев ниже, чтобы иметь смысл.

Answer 2

Математически, если у вас есть конечное множество (X, размера n (n натуральных чисел) и оператор сравнения (x, y, z в X; x <= y и y <= z означает x <= z)Это очень простая задача - найти максимальное значение. (Кроме того, оно существует.) </p>

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

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

Часть 2. Далее нам нужно преобразовать каждое двоичное число в заданный тип. Эта задачагде моя неопытность в программировании делает меня неспособным говорить о том, как это может быть достигнуто. Я читал кое-что о приведении, может быть, это поможет? Или какой-то другой метод преобразования?

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

Но что, если ...

... мы не знаем точное число членов данного типа?Чем мы переоцениваем.Если мы не сможем дать разумную завышенную оценку, тогда число должно быть физическим.Получив завышенную оценку, мы проверяем все возможные битовые шаблоны, чтобы подтвердить, какие битовые шаблоны представляют элементы типа.После отбрасывания тех, которые не используются, у нас теперь есть набор всех возможных битовых комбинаций, которые представляют некоторый член данного типа.Этот последний сгенерированный набор - это то, что мы использовали бы сейчас в части 1.

... у нас нет оператора сравнения в этом типе?Чем конкретная проблема не только невозможна, но и логически неактуальна.То есть, если у нашей программы нет доступа к значимому результату, если мы сравниваем два значения из нашего данного типа, тогда у нашего данного типа нет порядка в контексте нашей программы.Без упорядочения нет такого понятия, как максимальное значение.

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

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

... мы хотим оптимизировать проблему?Затем нам понадобится некоторая информация о том, как данный тип отображается из двоичных чисел.Например, unsigned int, подписанный int (комплимент 2) и подписанный int (комплимент 1) каждая карта из битов в числа очень документированным и простым способом.Таким образом, если мы хотели получить максимально возможное значение для unsigned int и знали, что работаем с m битами, то мы могли бы просто заполнить каждый бит 1, преобразовать битовую комбинацию в десятичную и вывести число.

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

Удачи.

Answer 3

Обновление: К счастью, мой предыдущий ответ ниже был неправильным, и, кажется, есть решение этого вопроса.

intmax_t x;
for (x=INTMAX_MAX; (T)x!=x; x/=2);

Эта программа либо выдает x, содержащую максимумвозможное значение типа T или генерирует сигнал, определяемый реализацией.

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

Интересная часть, особенно если вам удобно предполагать, что у вас нет реализации, которая будет генерировать сигнал, - это то, что происходит, когда (T)x приводит к преобразованию, определяемому реализацией.,Уловка вышеуказанного цикла заключается в том, что он вообще не зависит от выбора значения реализации для преобразования.Все, на что он полагается, это то, что (T)x==x возможно тогда и только тогда, когда x соответствует типу T, поскольку в противном случае значение x находится вне диапазона возможных значений любого выражения введите T.

---

Старая идея, неверная, поскольку она не учитывает указанное выше свойство (T)x==x:

Мне кажется, у меня есть набросокдоказательство того, что то, что я ищу, невозможно:

1. Позвольте X быть соответствующей реализацией C и предположим INT_MAX>32767.
2. Определите новую реализацию C, идентичную X,но где значения INT_MAX и INT_MIN делятся на 2.
3. Докажите, что Y является соответствующей реализацией C.

Основная идея этой схемы заключается в том, что, из-за того, что все, что связано со значениями вне границ со знаковыми типами, является поведением, определяемым реализацией, или неопределенным поведением, произвольное число старших битов значения целого типа со знаком может рассматриваться как набивочные биты без приводаy вносить какие-либо изменения в реализацию, кроме макросов предела в limits.h.

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

Answer 4

Я мог бы просто писать глупости здесь, поскольку я относительно новичок в C, но разве это не сработает для получения максимума signed?

unsigned x = ~0;
signed y=x/2;

Это может быть глупый способ сделать это, но, насколько я видел, unsigned max значения равны signed max* 2 + 1. Разве это не сработает в обратном направлении?

Извините за потраченное время, если это окажется совершенно неадекватным и неправильным.

Answer 5

Может быть, я не совсем правильно понял вопрос, но поскольку C дает вам 3 возможных представления целых чисел со знаком (http://port70.net/~nsz/c/c11/n1570.html#6.2.6.2):

• знак и величина
• дополнение к одному
• дополняют два

, и максимум в любом из них должен быть 2^(N-1)-1, вы должны быть в состоянии получить его, взяв максимум соответствующего без знака, >>1 -shiftingэто и приведение результата к правильному типу (который он должен соответствовать).

Я не знаю, как получить соответствующий минимум, если представления ловушек мешают, но если они этого не делают, мин долженбыть либо (Tp)((Tp)-1|(Tp)TP_MAX(Tp)) (все биты установлены) (Tp)~TP_MAX(Tp) и узнать его просто.

Пример:

#include <limits.h>
#define UNSIGNED(Tp,Val) \
    _Generic((Tp)0, \
            _Bool: (_Bool)(Val), \
            char: (unsigned char)(Val), \
            signed char: (unsigned char)(Val), \
            unsigned char: (unsigned char)(Val), \
            short: (unsigned short)(Val), \
            unsigned short: (unsigned short)(Val), \
            int: (unsigned int)(Val), \
            unsigned int: (unsigned int)(Val), \
            long: (unsigned long)(Val), \
            unsigned long: (unsigned long)(Val), \
            long long: (unsigned long long)(Val), \
            unsigned long long: (unsigned long long)(Val) \
            )
#define MIN2__(X,Y) ((X)<(Y)?(X):(Y))
#define UMAX__(Tp) ((Tp)(~((Tp)0)))
#define SMAX__(Tp) ((Tp)( UNSIGNED(Tp,~UNSIGNED(Tp,0))>>1 ))
#define SMIN__(Tp) ((Tp)MIN2__( \
                    (Tp)(((Tp)-1)|SMAX__(Tp)), \
                    (Tp)(~SMAX__(Tp)) ))
#define TP_MAX(Tp) ((((Tp)-1)>0)?UMAX__(Tp):SMAX__(Tp))
#define TP_MIN(Tp) ((((Tp)-1)>0)?((Tp)0): SMIN__(Tp))
int main()
{
#define STC_ASSERT(X) _Static_assert(X,"")
    STC_ASSERT(TP_MAX(int)==INT_MAX);
    STC_ASSERT(TP_MAX(unsigned int)==UINT_MAX);
    STC_ASSERT(TP_MAX(long)==LONG_MAX);
    STC_ASSERT(TP_MAX(unsigned long)==ULONG_MAX);
    STC_ASSERT(TP_MAX(long long)==LLONG_MAX);
    STC_ASSERT(TP_MAX(unsigned long long)==ULLONG_MAX);

    /*STC_ASSERT(TP_MIN(unsigned short)==USHRT_MIN);*/
    STC_ASSERT(TP_MIN(int)==INT_MIN);
    /*STC_ASSERT(TP_MIN(unsigned int)==UINT_MIN);*/
    STC_ASSERT(TP_MIN(long)==LONG_MIN);
    /*STC_ASSERT(TP_MIN(unsigned long)==ULONG_MIN);*/
    STC_ASSERT(TP_MIN(long long)==LLONG_MIN);
    /*STC_ASSERT(TP_MIN(unsigned long long)==ULLONG_MIN);*/

    STC_ASSERT(TP_MAX(char)==CHAR_MAX);
    STC_ASSERT(TP_MAX(signed char)==SCHAR_MAX);
    STC_ASSERT(TP_MAX(short)==SHRT_MAX);
    STC_ASSERT(TP_MAX(unsigned short)==USHRT_MAX);

    STC_ASSERT(TP_MIN(char)==CHAR_MIN);
    STC_ASSERT(TP_MIN(signed char)==SCHAR_MIN);
    STC_ASSERT(TP_MIN(short)==SHRT_MIN);
}

Answer 6

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

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

#define MAXVAL(T) (((((T) 1 << (sizeof(T) * CHAR_BIT - 2)) - 1) * 2) + 1)

Это, наверное, лучшее, что можно сделать. Это просто и не нужно предполагать что-либо еще о реализации C.

Answer 7

Прежде чем задать вопрос «Как?» , сначала вам нужно задать вопрос «Почему?» . Почему вы действительно должны знать это во время выполнения? Это связано с реальной проблемой или это просто академический вопрос?

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

Answer 8

Почему это представляет проблему? Размер типа фиксируется во время компиляции, поэтому проблема определения размера типа во время выполнения сводится к задаче определения размера типа во время компиляции. Для любой конкретной целевой платформы объявление, такое как off_t offset, будет скомпилировано с использованием некоторого фиксированного размера, и этот размер будет всегда использоваться при запуске результирующего исполняемого файла на целевой платформе.

ETA: Вы можете получить размер типа type через sizeof(type). Затем вы можете сравнить с общими целочисленными размерами и использовать соответствующее определение препроцессора MAX / MIN. Возможно, вам будет проще просто использовать:

uintmax_t bitWidth = sizeof(type) * CHAR_BIT;
intmax_t big2 = 2;  /* so we do math using this integer size */
intmax_t sizeMax = big2^bitWidth - 1;
intmax_t sizeMin = -(big2^bitWidth - 1);

То, что значение представляется базовым «физическим» типом, не означает, что это значение допустимо для значения «логического» типа. Я предполагаю, что причина, по которой константы max и min не указаны, заключается в том, что это «полупрозрачные» типы, использование которых ограничено конкретными доменами. Там, где желательна меньшая непрозрачность, вы часто найдете способы получения необходимой информации, например, константы, которые вы можете использовать, чтобы выяснить, насколько велика off_t, упомянутая SUSv2 в его описании <unistd.h>.

Answer 9

Поскольку вы позволяете этому быть во время выполнения, вы можете написать функцию, которая де-факто выполняет итеративный сдвиг влево (type)3.Если вы остановитесь, когда значение упадет ниже 0, это никогда не даст вам представление ловушки.А количество итераций - 1 сообщит вам положение знакового бита.

Остается проблема с левым сдвигом.Поскольку простое использование оператора << приведет к переполнению, это будет неопределенное поведение, поэтому мы не можем использовать оператор напрямую.

Самое простое решение этого вопроса - не использовать сдвинутый 3как и выше, но для итерации по позициям битов и добавления также всегда младшего значащего бита.

type x;
unsigned char*B = &x;
size_t signbit = 7;
for(;;++signbit) {
  size_t bpos = signbit / CHAR_BIT;
  size_t apos = signbit % CHAR_BIT;
  x = 1;
  B[bpos] |= (1 << apos);
  if (x < 0) break;
}

(Начальное значение 7 - это минимальная ширина, которую должен иметь подписанный тип, я думаю).

Answer 10

Предполагая, что изменение битов заполнения не создаст представления ловушек, вы можете использовать unsigned char *, чтобы зацикливаться и переворачивать отдельные биты до тех пор, пока не достигнете знакового бита.Если ваше начальное значение было ~(type)0, это должно дать вам максимум:

type value = ~(type)0;
assert(value < 0);

unsigned char *bytes = (void *)&value;
size_t i = 0;
for(; i < sizeof value * CHAR_BIT; ++i)
{
    bytes[i / CHAR_BIT] ^= 1 << (i % CHAR_BIT);
    if(value > 0) break;
    bytes[i / CHAR_BIT] ^= 1 << (i % CHAR_BIT);
}

assert(value != ~(type)0);
// value == TYPE_MAX