Как определить, сколько байтов нужно целому числу? - PullRequest
Новая
       34

Как определить, сколько байтов нужно целому числу?

25 голосов
/ 16 февраля 2010

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

e.g.

int: 10 = 1 byte
int: 257 = 2 bytes;
int: 18446744073709551615 (UINT64_MAX) = 8 bytes;

Спасибо

P.S. Это для хеш-функций, которые будут вызываться много миллионов раз

Кроме того, размеры байтов не должны быть степенью двойки

Самое быстрое решение, кажется, основанное на ответе tronics: 

    int bytes;
    if (hash <= UINT32_MAX) 
    {
        if (hash < 16777216U)
        {
            if (hash <= UINT16_MAX)
            {
                if (hash <= UINT8_MAX) bytes = 1;
                else bytes = 2;
            }
            else bytes = 3;
        }
        else bytes = 4;
    } 
    else if (hash <= UINT64_MAX) 
    {
        if (hash < 72057594000000000ULL) 
        {
            if (hash < 281474976710656ULL) 
            {
                if (hash < 1099511627776ULL) bytes = 5;
                else bytes = 6;
            }
            else bytes = 7;
        }
        else bytes = 8;
    }

Разница в скорости, использующая в основном 56-битные значения, была минимальной (но измеримой) по сравнению с ответом Томаса Порнина. Также я не тестировал решение, используя __builtin_clzl, который мог бы быть сравним.

Ответы [ 22 ]

29 голосов
/ 16 февраля 2010

Используйте это: 

int n = 0;
while (x != 0) {
    x >>= 8;
    n ++;
}

Предполагается, что x содержит ваше (положительное) значение.

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

20 голосов
/ 16 февраля 2010

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

if (val < 0x10000) {
    if (val < 0x100) // 8 bit
    else // 16 bit
} else {
    if (val < 0x100000000L) // 32 bit
    else // 64 bit
}

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

9 голосов
/ 16 февраля 2010

Сначала вы можете получить максимальный набор битов, равный log2 (N), а затем получить байты, необходимые для ceil (log2 (N) / 8).

Вот некоторые битовые хаки для получения позиции наибольшего набора битов, которые скопированы из http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious,, и вы можете щелкнуть URL-адрес, чтобы узнать, как работают эти алгоритмы.

Найти целочисленную логарифмическую базу 2 целого числа с 64-разрядным IEEE-числом с плавающей запятой 

int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

Найти лог-базу 2 целого числа с таблицей поиска 

static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

Найти логическую базу 2 N-разрядного целого числа в O (lg (N)) операциях 

unsigned int v;  // 32-bit value to find the log2 of 
const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
const unsigned int S[] = {1, 2, 4, 8, 16};
int i;

register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
  if (v & b[i])
  {
    v >>= S[i];
    r |= S[i];
  } 
}


// OR (IF YOUR CPU BRANCHES SLOWLY):

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);


// OR (IF YOU KNOW v IS A POWER OF 2):

unsigned int v;  // 32-bit value to find the log2 of 
static const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 
                                 0xFF00FF00, 0xFFFF0000};
register unsigned int r = (v & b[0]) != 0;
for (i = 4; i > 0; i--) // unroll for speed...
{
  r |= ((v & b[i]) != 0) << i;
}
9 голосов
/ 16 февраля 2010

Предполагая, что байт равен 8 битам, для представления целого числа x вам нужно [log2 (x) / 8] + 1 байт, где [x] = пол (x).

Хорошо, теперь я вижу, что размеры байтов не обязательно являются степенью двойки. Рассмотрим размеры байтов б. Формула по-прежнему [log2 (x) / b] + 1.

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

9 голосов
/ 16 февраля 2010

Функция поиска позиции первого бита '1' с самой старшей стороны (clz или bsr) обычно представляет собой простую инструкцию ЦП (не нужно связываться с журналом 2 ), так что вы можете разделить это на 8, чтобы получить необходимое количество байтов. В gcc для этой задачи есть __builtin_clz: 

#include <limits.h>
int bytes_needed(unsigned long long x) {
   int bits_needed = sizeof(x)*CHAR_BIT - __builtin_clzll(x);
   if (bits_needed == 0)
      return 1;
   else
      return (bits_needed + 7) / 8;
}

(В MSVC вы должны использовать _BitScanReverse встроенный .)

5 голосов
/ 16 февраля 2010

Найдите количество бит, взяв лог 2 числа, затем разделите его на 8, чтобы получить количество байтов.

Вы можете найти лог n x по формуле:

log n (x) = log (x) / log (n)

Обновление:

Поскольку вам нужно сделать это очень быстро, Bit Twiddling Hacks имеет несколько методов для быстрого вычисления лога 2 (x). Подход с помощью таблицы поиска выглядит так, как будто он соответствует вашим потребностям.

4 голосов
/ 16 февраля 2010

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

template<unsigned long long N> struct NBytes
{ static const size_t value = NBytes<N/256>::value+1; };
template<> struct NBytes<0> 
{ static const size_t value = 0; };

int main()
{
    std::cout << "short = " << NBytes<SHRT_MAX>::value << " bytes\n";
    std::cout << "int = " << NBytes<INT_MAX>::value << " bytes\n";
    std::cout << "long long = " << NBytes<ULLONG_MAX>::value << " bytes\n";
    std::cout << "10 = " << NBytes<10>::value << " bytes\n";
    std::cout << "257 = " << NBytes<257>::value << " bytes\n";
    return 0;
}

выход: 

short = 2 bytes
int = 4 bytes
long long = 8 bytes
10 = 1 bytes
257 = 2 bytes

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

4 голосов
/ 16 февраля 2010

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

int count = 0;
while (numbertotest > 0)
{
  numbertotest >>= 8;
  count++;
}
3 голосов
/ 16 февраля 2010

Я думаю, что это переносимая реализация простой формулы: 

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

int main(void) {
    int i;
    unsigned int values[] = {10, 257, 67898, 140000, INT_MAX, INT_MIN};

    for ( i = 0; i < sizeof(values)/sizeof(values[0]); ++i) {
        printf("%d needs %.0f bytes\n",
                values[i],
                1.0 + floor(log(values[i]) / (M_LN2 * CHAR_BIT))
              );
    }
    return 0;
}

Выход: 

10 needs 1 bytes
257 needs 2 bytes
67898 needs 3 bytes
140000 needs 3 bytes
2147483647 needs 4 bytes
-2147483648 needs 4 bytes

Будет ли отсутствие скорости и необходимость связывать библиотеки с плавающей точкой зависеть от ваших потребностей.

3 голосов
/ 16 февраля 2010

Вам нужна именно функция журнала

nb_bytes = этаж (журнал (х) / журнал (256)) + 1 если вы используете log2, log2 (256) == 8, так что

этаж (log2 (х) / 8) + 1

Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...