Программное определение максимального значения целочисленного типа со знаком
Этот связанный вопрос касается определения максимального значения типа со знаком во время компиляции:
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 имеет биты заполнения, приведение вызывает поведение, определяемое реализацией, которое может быть сигналом или бессмысленным преобразованием, определяемым реализацией (например, удаление знакового бита).
Я начинаю думать, что проблема неразрешима, что немного тревожит и, по моему мнению, будет дефектом стандарта Си. Есть идеи, чтобы доказать, что я не прав?
11 ответов
Обновление: К счастью, мой предыдущий ответ ниже был неправильным, и, кажется, есть решение этого вопроса.
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 имущество:
Я думаю, что у меня есть набросок доказательства того, что то, что я ищу, невозможно:
- Пусть X будет соответствующей реализацией C и предположим,
INT_MAX>32767, - Определите новую реализацию C, идентичную X, но где значения
INT_MAXа такжеINT_MINкаждый делится на 2. - Докажите, что Y соответствует C-реализации.
Основная идея этой схемы заключается в том, что из-за того, что все, что связано со значениями вне границ со знаковыми типами, является поведением, определяемым реализацией, или неопределенным поведением, можно рассматривать произвольное число старших битов со знаком целочисленного типа. как заполнение битов без фактического внесения каких-либо изменений в реализацию, за исключением предельных макросов в limits.h,
Есть мысли о том, звучит ли это правильно или фальшиво? Если это правильно, я был бы рад присуждать награду тому, кто сможет сделать ее более строгой.
Давайте сначала посмотрим, как C определяет "целочисленные типы". Взято из ISO / IEC 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, и тадаа, у нас есть максимально возможное int значение.
Определение int минимум немного сложнее и оставлен читателю в качестве упражнения.
Обратите внимание, что стандарт С юмористически не требует двух разных ints вести себя так же. Если я не ошибаюсь, может быть два разных int объекты, которые имеют, например, свои соответствующие знаковые биты в разных позициях.
РЕДАКТИРОВАТЬ: обсуждая этот подход с R.. (см. Комментарии ниже), я убедился, что он имеет недостатки в нескольких отношениях и, в более общем плане, что нет никакого решения вообще. Я не вижу способа исправить это сообщение (кроме как удалить его), поэтому я оставил его без изменений для комментариев ниже, чтобы иметь смысл.
Математически, если у вас есть конечное множество (X, размера n (n натуральных чисел) и оператор сравнения (x,y,z в X; x<=y и y<=z подразумевает x<=z), это Очень простая задача найти максимальное значение. (Также оно существует.)
Самый простой способ решить эту проблему, но самый затратный в вычислительном отношении - это создать массив со всеми возможными значениями, а затем найти максимальное значение.
Часть 1. Для любого типа с конечным набором элементов существует конечное число бит (m), которое можно использовать для уникального представления любого данного члена этого типа. Мы просто создаем массив, который содержит все возможные битовые комбинации, где любой данный битовый шаблон представлен заданным значением в конкретном типе.
Часть 2. Далее нам нужно будет преобразовать каждое двоичное число в заданный тип. Эта задача - то, где моя неопытность в программировании делает меня неспособным говорить о том, как это может быть достигнуто. Я читал некоторые о кастинге, может быть, это поможет? Или какой-то другой метод конвертации?
Часть 3. Предполагая, что предыдущий шаг был завершен, у нас теперь есть конечный набор значений в нужном типе и оператор сравнения для этого набора. Найти макс.
Но что, если...
... мы не знаем точное количество членов данного типа? Чем мы переоцениваем. Если мы не сможем дать разумную завышенную оценку, тогда число должно быть физическим. Как только мы получим завышенную оценку, мы проверяем все возможные битовые шаблоны, чтобы подтвердить, какие битовые шаблоны представляют элементы типа. После отбрасывания тех, которые не используются, у нас теперь есть набор всех возможных битовых комбинаций, которые представляют некоторый член данного типа. Этот последний сгенерированный набор - это то, что мы сейчас будем использовать в первой части.
... у нас нет оператора сравнения в этом типе? Чем конкретная проблема не только невозможна, но и логически неактуальна. То есть, если у нашей программы нет доступа к значимому результату, если мы сравниваем два значения из нашего данного типа, тогда у нашего данного типа нет порядка в контексте нашей программы. Без заказа нет такого понятия, как максимальное значение.
... мы не можем преобразовать данное двоичное число в данный тип? Тогда метод ломается. Но, как и в предыдущем исключении, если вы не можете конвертировать типы, наш набор инструментов выглядит логически очень ограниченным.
Технически вам может не потребоваться преобразовывать двоичные представления в определенный тип. Весь смысл преобразования заключается в том, чтобы сгенерированный список был исчерпывающим.
... мы хотим оптимизировать проблему? Затем нам понадобится некоторая информация о том, как данный тип отображается из двоичных чисел. Например, unsigned int, подписанный int (комплимент 2) и подписанный int (комплимент 1) каждая карта из битов в числа очень документированным и простым способом. Таким образом, если мы хотели получить максимально возможное значение для unsigned int и знали, что работаем с m битами, то мы могли бы просто заполнить каждый бит 1, преобразовать битовую комбинацию в десятичную, а затем вывести число.
Это относится к оптимизации, потому что наиболее дорогой частью этого решения является список всех возможных ответов. Если у нас есть некоторые предварительные знания о том, как данный тип отображается из битовых комбинаций, мы можем сгенерировать подмножество всех возможностей, сделав вместо этого всех потенциальных кандидатов.
Удачи.
Я мог бы просто писать глупости здесь, так как я относительно новичок в C, но разве это не поможет получить максимум signed?
unsigned x = ~0;
signed y=x/2;
Это может быть глупый способ сделать это, но, насколько я видел unsigned max значения signed max*2+1. Разве это не сработает?
Извините за потраченное время, если это окажется совершенно неадекватным и неправильным.
Для всех реальных машин (дополнение до двух и без отступов):
type tmp = ((type)1)<< (CHAR_BIT*sizeof(type)-2);
max = tmp + (tmp-1);
С C++ вы можете рассчитать его во время компиляции.
template <class T>
struct signed_max
{
static const T max_tmp = T(T(1) << sizeof(T)*CO_CHAR_BIT-2u);
static const T value = max_tmp + T(max_tmp -1u);
};
Предполагая, что изменение битов заполнения не создаст представления ловушек, вы можете использовать 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
Разве не должен делать что-то вроде следующего псевдокода?
signed_type_of_max_size test_values =
[(1<<7)-1, (1<<15)-1, (1<<31)-1, (1<<63)-1];
for test_value in test_values:
signed_foo_t a = test_value;
signed_foo_t b = a + 1;
if (b < a):
print "Max positive value of signed_foo_t is ", a
Или намного проще, почему не должно работать следующее?
signed_foo_t signed_foo_max = (1<<(sizeof(signed_foo_t)*8-1))-1;
Что касается моего собственного кода, я бы определенно пошел на проверку во время сборки, определяя макрос препроцессора.
Почему это представляет проблему? Размер типа фиксируется во время компиляции, поэтому проблема определения размера типа во время выполнения сводится к задаче определения размера типа во время компиляции. Для любой целевой платформы, объявление, такое как 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>,
Возможно, я не правильно понял вопрос, но поскольку C дает вам 3 возможных представления целых чисел со знаком ( http://port70.net/~nsz/c/c11/n1570.html):
- знак и величина
- свои дополнения
- дополнение двух
и максимум в любом из них должен быть 2^(N-1)-1, вы должны быть в состоянии получить его, взяв максимум соответствующего неподписанного, >>1 - сдвинув его и приведя результат к нужному типу (который должен соответствовать).
Я не знаю, как получить соответствующий минимум, если мешающие представления мешают, но если они этого не делают, мин должен быть либо (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);
}
Поскольку вы допускаете это во время выполнения, вы можете написать функцию, которая де-факто выполняет итеративный сдвиг влево (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 это минимальная ширина, которую должен иметь подписанный тип, я думаю).
Для непрозрачного подписанного типа, для которого у вас нет имени связанного беззнакового типа, это неразрешимо переносимым способом, потому что любая попытка обнаружить, есть ли бит заполнения, приведет к поведению, определяемому реализацией, или неопределенному поведению. Лучшее, что вы можете сделать из тестирования (без дополнительных знаний), - это наличие как минимум K битов заполнения.
Кстати, это на самом деле не отвечает на вопрос, но все же может быть полезно на практике: если предположить, что целочисленный тип со знаком T не имеет битов заполнения, можно использовать следующий макрос:
#define MAXVAL(T) (((((T) 1 << (sizeof(T) * CHAR_BIT - 2)) - 1) * 2) + 1)
Это, наверное, лучшее, что можно сделать. Это просто и не нужно предполагать что-либо еще о реализации C.
Прежде чем задать вопрос "Как?" сначала нужно задать вопрос "почему?", Почему вы действительно должны знать это во время выполнения? Это связано с реальной проблемой или это просто академический вопрос?
Я действительно не вижу необходимости определять это во время компиляции. Если программист пишет программу для удовлетворения конкретных потребностей, он определенно обладает знаниями о среде, в которой она будет выполняться.