Как определить, сколько байтов нужно целому числу? - PullRequest
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 ]

0 голосов
/ 23 декабря 2016

Почему так сложно? Вот что я придумал:

bytesNeeded = (numBits/8)+((numBits%8) != 0);

В основном numBits делится на восемь + 1, если есть остаток.

0 голосов
/ 11 сентября 2011

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

inline int get_num_bytes(unsigned long long value) // where unsigned long long is the largest integer value on this platform
{
    int size = 1; // starts at 1 sot that 0 will return 1 byte

    size += !!(value & 0xFF00);
    size += !!(value & 0xFFFF0000);
    if (sizeof(unsigned long long) > 4) // every sane compiler will optimize this out
    {
        size += !!(value & 0xFFFFFFFF00000000ull);
        if (sizeof(unsigned long long) > 8)
        {
            size += !!(value & 0xFFFFFFFFFFFFFFFF0000000000000000ull);
        }
    }

    static const int size_table[] = { 1, 2, 4, 8, 16 };
    return size_table[size];
}

g ++ -O3 производит следующее (проверяя, оптимизированы ли ifs):

xor    %edx,%edx
test   $0xff00,%edi
setne  %dl
xor    %eax,%eax
test   $0xffff0000,%edi
setne  %al
lea    0x1(%rdx,%rax,1),%eax
movabs $0xffffffff00000000,%rdx
test   %rdx,%rdi
setne  %dl
lea    (%rdx,%rax,1),%rax
and    $0xf,%eax
mov    _ZZ13get_num_bytesyE10size_table(,%rax,4),%eax
retq
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...