Вопрос по string, c – ANSI-C: максимальное количество символов, печатающих десятичное целое

10

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

я знаю<limits.h> содержит такие определения, какINT_MAX что сказать максимумvalue int может предположить, но это не то, что я хочу.

Я хотел бы иметь возможность сделать что-то вроде:

int get_int( void )
{
    char draft[ MAX_CHAR_OF_A_DECIMAL_INT ];

    fgets( draft, sizeof( draft ), stdin );
    return strtol( draft, NULL, 10 );
}

Но как найти значениеMAX_CHAR_OF_A_DECIMAL_INT в переносном и низко перегруженном виде?

Спасибо!

Не могли бы вы взять INT_MAX, преобразовать в строку и посчитать длину, а затем добавить один (чтобы включить ведущий -) Tyler Eaves
Предположительно, вам на самом деле не нужна максимально возможная длина, просто число, большее или равное этому, и не настолько большое, чтобы быть очень расточительным?BIG_ENOUGH_FOR_AN_INT, скорее, чемBIGGEST_AN_INT_CAN_BE. Steve Jessop

Ваш Ответ

6   ответов
4

Самый простой канонический и, возможно, самый переносимый способ - это спроситьsnprintf() сколько места потребуется:

char sbuf[2];
int ndigits;

ndigits = snprintf(sbuf, (size_t) 1, "%lld", (long long) INT_MIN);

чуть менее портативный, возможно, используяintmax_t а также%j:

ndigits = snprintf(sbuf, (size_t) 1, "%j", (intmax_t) INT_MIN);

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

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

unsigned int
numCharsB10(intmax_t n)
{
        if (n < 0)
                return numCharsB10((n == INTMAX_MIN) ? INTMAX_MAX : -n) + 1;
        if (n < 10)
                return 1;

        return 1 + numCharsB10(n / 10);
}

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

Ответ @ R., приведенный выше, хотя и более-менее неправильный, но на правильном пути. Вот правильный вывод некоторых очень хорошо и широко протестированных и очень переносимых макросов, которые реализуют вычисления во время компиляции, используяsizeof()используя небольшую коррекцию исходной формулировки @ R. для начала:

Сначала мы можем легко увидеть (или показать), чтоsizeof(int) является основой журнала 2 изUINT_MAX делится на количество битов, представленных одной единицейsizeof() (8, акаCHAR_BIT):

sizeof (int) == log2 (UINT_MAX) / 8

так какUINT_MAX конечно, только 2 ^ (sizeof (int) * 8)), а log2 (x) является обратным 2 ^ x.

Мы можем использовать идентификатор "logb (x) = log (x) / log (b)" (где log () - натуральный логарифм), чтобы найти логарифмы других оснований. Например, вы можете вычислить «log base 2» из "х" с помощью:

log2 (x) = log (x) / log (2)

а также:

log10 (x) = log (x) / log (10)

Итак, мы можем сделать вывод, что:

log10 (v) = log2 (v) / log2 (10)

Теперь то, что мы хотим в конце концов, это база 10 журналовUINT_MAX, так как log2 (10) составляет приблизительно 3, и так как мы знаем сверху, что log2 () с точки зренияsizeof()можно сказать что log10 (UINT_MAX) примерно:

log10 (2 ^ (sizeof (int) * 8)) ~ = (sizeof (int) * 8) / 3

Это не идеально, тем более что нам действительно нужно предельное значение, но с некоторой незначительной корректировкой для учета целочисленного округления log2 (10) до 3, мы можем получить то, что нам нужно, сначала добавив единицу в log2 термин, затем вычитая 1 из результата для любого целого числа большего размера, что приводит к этому "достаточно хорошему" выражение:

#if 0
#define __MAX_B10STRLEN_FOR_UNSIGNED_TYPE(t) \
    ((((sizeof(t) * CHAR_BIT) + 1) / 3) - ((sizeof(t) > 2) ? 1 : 0))
#endif

Более того, мы можем умножить наш первый член log2 () на 1 / log2 (10) (умножение на обратную величину делителя равно делению на делитель), и это позволяет найти лучшее целочисленное приближение. Я недавно (повторно?) Столкнулся с этим предложением, читая битхаки Шона Андерсона:http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10

Чтобы сделать это с целочисленной математикой до наилучшего возможного приближения, нам нужно найти идеальное соотношение, представляющее нашу обратную величину. Это может быть найдено путем поиска наименьшей дробной части умножения желаемого значения 1 / log2 (10) на последовательные степени 2 в некотором разумном диапазоне степеней 2, например, с помощью следующего небольшого скрипта AWK:

    awk 'BEGIN {
            minf=1.0
    }
    END {
            for (i = 1; i <= 31; i++) {
                    a = 1.0 / (log(10) / log(2)) * 2^i
                    if (a > (2^32 / 32))
                            break;
                    n = int(a)
                    f = a - (n * 1.0)
                    if (f < minf) {
                            minf = f
                            minn = n
                            bits = i
                    }
                    # printf("a=%f, n=%d, f=%f, i=%d\n", a, n, f, i)
            }
            printf("%d + %f / %d, bits=%d\n", minn, minf, 2^bits, bits)
    }' < /dev/null

    1233 + 0.018862 / 4096, bits=12

Таким образом, мы можем получить хорошее целочисленное приближение умножения нашего значения log2 (v) на 1 / log2 (10), умножив его на 1233 с последующим сдвигом вправо на 12 (2 ^ 12, конечно, 4096):

log10 (UINT_MAX) ~ = ((sizeof (int) * 8) + 1) * 1233 & gt; 12

и, вместе с добавлением единицы для поиска максимального значения, это избавляет от необходимости возиться с нечетными значениями:

#define __MAX_B10STRLEN_FOR_UNSIGNED_TYPE(t) \
    (((((sizeof(t) * CHAR_BIT)) * 1233) >> 12) + 1)

/*
 * for signed types we need room for the sign, except for int64_t
 */
#define __MAX_B10STRLEN_FOR_SIGNED_TYPE(t) \
    (__MAX_B10STRLEN_FOR_UNSIGNED_TYPE(t) + ((sizeof(t) == 8) ? 0 : 1))

/*
 * NOTE: this gives a warning (for unsigned types of int and larger) saying
 * "comparison of unsigned expression < 0 is always false", and of course it
 * is, but that's what we want to know (if indeed type 't' is unsigned)!
 */
#define __MAX_B10STRLEN_FOR_INT_TYPE(t)                     \
    (((t) -1 < 0) ? __MAX_B10STRLEN_FOR_SIGNED_TYPE(t)      \
                  : __MAX_B10STRLEN_FOR_UNSIGNED_TYPE(t))

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

Лучший ответ здесь. Очень нравится, спасибо!
11

Если вы предполагаетеCHAR_BIT равно 8 (требуется для POSIX, поэтому безопасное допущение для любого кода, предназначенного для систем POSIX, а также для любой другой основной системы, такой как Windows), дешевая безопасная формула3*sizeof(int)+2, Если нет, вы можете сделать это3*sizeof(int)*CHAR_BIT/8+2или существует несколько более простая версия.

Если вас интересует причина, по которой это работает,sizeof(int) по сути логарифмINT_MAX (примерно логарифмическое основание 2 ^ CHAR_BIT), и преобразование между логарифмами разных оснований (например, в основание 10) является просто умножением. В частности, 3 представляет собой целочисленное приближение / верхнюю границу для логарифмической базы 10 из 256.

+2 должен учитывать возможный знак и нулевое завершение.

это не совсем верно, но на правильном пути ....
Вывод: для представления десятичной цифры требуется в среднем 3,2 бита; каждый 8-битный байт может представлять в среднем 2,5 десятичных знака; округление дает 3 (следовательно,3 * sizeof (int)). Затем вам нужен дополнительный символ для знака и дополнительный символ для терминатора 0 (отсюда+ 2).
2

После принятия ответа (2+ года)

Следующая фракция 10/33 точно соответствует потребностям без прокладкиint8_t, int16_t, int32_t а такжеint128_t, Только 1char дополнительно дляint64_t, Точный или 1 для всех целых размеров доint362_t, За этим может быть больше, чем 1.

#include <limits.h>
#define MAX_CHAR_LEN_DECIMAL_INTEGER(type) (10*sizeof(type)*CHAR_BIT/33 + 2)
#define MAX_CHAR_SIZE_DECIMAL_INTEGER(type) (10*sizeof(type)*CHAR_BIT/33 + 3)

int get_int( void ) {
                                            //   + 1 for the \n of fgets()
  char draft[MAX_CHAR_SIZE_DECIMAL_INTEGER(long) + 1];  //**

  fgets(draft, sizeof draft, stdin);
  return strtol(draft, NULL, 10);
}

** fgets() как правило, лучше всего работает с дополнительнымchar для прекращения'\n'.

Похожий на@Р.. но с лучшей долей.


Рекомендуем использовать щедрые, 2x, буферы при чтении пользовательского ввода. Иногда пользователь добавляет пробелы, ведущие нули и т. Д.

  char draft[2*(MAX_CHAR_SIZE_DECIMAL_INTEGER(long) + 1)];
  fgets(draft, sizeof draft, stdin);
2

Я не знаю, если это какой-то трюк, чтобы делать то, что вы хотите в простом ANSI-C, но в C ++ вы можете легко использовать метапрограммирование шаблонов, чтобы сделать:

#include    <iostream>
#include    <limits>
#include    <climits>

template< typename T, unsigned long N = INT_MAX >
class   MaxLen
{
public:
    enum
    {
        StringLen = MaxLen< T, N / 10 >::StringLen + 1
    };
};

template< typename T >
class   MaxLen< T, 0 >
{
public:
    enum
    {
        StringLen = 1
    };
};

И вы можете вызвать его из своего кода на чистом C, создав дополнительную функцию C ++, например:

extern "C"
int int_str_max( )
{
    return  MaxLen< int >::StringLen;
}

Это имеет нулевые накладные расходы на выполнение и вычисляет точное необходимое пространство.


Вы можете проверить вышеуказанные шаблоны с чем-то вроде:

int main( )
{
std::cout << "Max: " << std::numeric_limits< short >::max( ) << std::endl;
std::cout << "Digits: " << std::numeric_limits< short >::digits10 << std::endl;
std::cout << "A \"short\" is " << sizeof( short ) << " bytes." << std::endl
    << "A string large enough to fit any \"short\" is "
    << MaxLen< short, SHRT_MAX >::StringLen << " bytes wide." << std::endl;

std::cout << "Max: " << std::numeric_limits< int >::max( ) << std::endl;
std::cout << "Digits: " << std::numeric_limits< int >::digits10 << std::endl;
std::cout << "An \"int\" is " << sizeof( int ) << " bytes." << std::endl
    << "A string large enough to fit any \"int\" is "
    << MaxLen< int >::StringLen << " bytes wide." << std::endl;

std::cout << "Max: " << std::numeric_limits< long >::max( ) << std::endl;
std::cout << "Digits: " << std::numeric_limits< long >::digits10 << std::endl;
std::cout << "A \"long\" is " << sizeof( long ) << " bytes." << std::endl
    << "A string large enough to fit any \"long\" is "
    << MaxLen< long, LONG_MAX >::StringLen << " bytes wide." << std::endl;

    return  0;
}

Выход:

Max: 32767
Digits: 4
A "short" is 2 bytes.
A string large enough to fit any "short" is 6 bytes wide.
Max: 2147483647
Digits: 9
An "int" is 4 bytes.
A string large enough to fit any "int" is 11 bytes wide.
Max: 9223372036854775807
Digits: 18
A "long" is 8 bytes.
A string large enough to fit any "long" is 20 bytes wide.
  • Note the slightly different values from std::numeric_limits< T >::digits10 and MaxLen< T, N >::StringLen, as the former does not take into account digits if if can't reach '9'. Of course you can use it and simply add two if you don't care wasting a single byte in some cases.

РЕДАКТИРОВАТЬ:

Некоторые могут найти странным, в том числе<climits>. If you can count with C++11, you won't need it, and will earn an additional simplicity:

#include    <iostream>
#include    <limits>

template< typename T, unsigned long N = std::numeric_limits< T >::max( ) >
class   MaxLen
{
public:
    enum
    {
        StringLen = MaxLen< T, N / 10 >::StringLen + 1
    };
};

template< typename T >
class   MaxLen< T, 0 >
{
public:
    enum
    {
        StringLen = 1
    };
};

Теперь вы можете использовать

MaxLen< short >::StringLen

вместо

MaxLen< short, SHRT_MAX >::StringLen

Хорошо, не так ли?

Во-первых, C ++! = C Во-вторых, это ужасная сложность сделать что-то, что можно сделать как на C, так и на C ++ в относительно простом выражении с использованием sizeof ().
Of course you can use it and simply add two if you don't care wasting a single byte in some -- why add 2 and not just 1 digit? Это для знака? это для пустого символа? Будь более явным.
Я думаю, что я могу жить сstd::numeric_limits< T >::digits10 + 2 и тратить впустую байт. Это кажется простым, но быстрым. Благодарю. j4x
0

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

#include <limits.h>
#include <stdio.h>
#include <math.h>

int main(void){
  printf("%d %d\n", INT_MAX, (int)floor(log10(INT_MAX)) + 3);

  return 0;
}

Также обратите внимание, что число байтовint может быть 2 или 4, и это 2 только в старых системах, так что вы можете рассчитать верхнюю границу и использовать ее в своей программе.

1

Вот версия C:

#include <limits.h>

#define xstr(s) str(s)
#define str(s) #s
#define INT_STR_MAX sizeof(xstr(INT_MAX))

char buffer[INT_STR_MAX];

Затем:

$ gcc -E -o str.cpp str.c
$ grep buffer str.cpp
char buffer[sizeof("2147483647")];

$ gcc -S -o str.S str.c
$ grep buffer str.S
    .comm   buffer,11,1
Ничто в стандарте не требует, чтобыINT_MAX быть дано в десятичном виде. В последнее время0x7FFFFFFF используется вместо

Похожие вопросы