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

Question

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

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, который мог бы быть сравним.

Answer 1

Вам нужно повысить 256 до последовательных степеней, пока результат не станет больше, чем ваше значение.

Например: (проверено на C #)

long long limit = 1;
int byteCount;

for (byteCount = 1; byteCount < 8; byteCount++) {
    limit *= 256;
    if (limit > value)
        break;
}

Если вы хотите, чтобы размеры байтов были толькобыть степенью двойки (если вы не хотите, чтобы 65 537 возвращало 3), замените byteCount++ на byteCount *= 2.

Answer 2

Этаж ((log2 (N) / 8) + 1) байтов

Answer 3

Есть множество способов сделать это.

Вариант № 1.

 int numBytes = 0;
 do {
     numBytes++;
 } while (i >>= 8);
 return (numBytes);

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

Однако это может быть не самым быстрым. Кроме того, вы можете попробовать серию операторов if ...

Для 32-битных целых чисел

if ((upper = (value >> 16)) == 0) {
    /* Bit in lower 16 bits may be set. */
    if ((high = (value >> 8)) == 0) {
        return (1);
    }
    return (2);
}

/* Bit in upper 16 bits is set */
if ((high = (upper >> 8)) == 0) {
    return (3);
}
return (4);

Для 64-битных целых чисел требуется другой уровень операторов if.

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

Answer 4

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

//Assuming v is the value that is being counted...
int l=0;
for(;v>>l*8;l++);

Answer 5

Есть множество отличных рецептов для подобных вещей на Страница Шона Андерсона "Bit Twiddling Hacks".

Answer 6

Почему бы просто не использовать 32-битный хеш?

Это будет работать почти на максимальной скорости везде.

Я не совсем понимаю, зачем нужен большой хеш. Если работает 4-байтовый хеш, почему бы не использовать его всегда? За исключением криптографических применений, у кого есть хеш-таблицы с более чем 2 ³² ведрами в любом случае?

Answer 7

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

Answer 8

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

Более кратко, минимальное количество байтов, которое вам нужно, равно ceil(min_bits/8), где min_bits - это индекс (i+1) старшего установленного бита.

Answer 9

Здесь уже есть много ответов, но если вы знаете число заранее, в c ++ вы можете использовать template для использования препроцессора.

template <unsigned long long N>
struct RequiredBytes {
    enum : int { value = 1 + (N > 255 ? RequiredBits<(N >> 8)>::value : 0) };
};

template <>
struct RequiredBytes<0> {
    enum : int { value = 1 };
};

const int REQUIRED_BYTES_18446744073709551615 = RequiredBytes<18446744073709551615>::value; // 8

или для версии с битами:

template <unsigned long long N>
struct RequiredBits {
    enum : int { value = 1 + RequiredBits<(N >> 1)>::value };
};

template <>
struct RequiredBits<1> {
    enum : int { value = 1 };
};

template <>
struct RequiredBits<0> {
    enum : int { value = 1 };
};

const int REQUIRED_BITS_42 = RequiredBits<42>::value; // 6

Answer 10

Это основано на идее SoapBox о создании решения, которое не содержит скачков, ветвлений и т. Д. К сожалению, его решение было не совсем правильным. Я принял дух, и вот 32-битная версия, 64-битные чеки можно легко применить при желании.

Функция возвращает количество байтов, необходимое для хранения заданного целого числа.

unsigned short getBytesNeeded(unsigned int value)
{
    unsigned short c = 0; // 0 => size 1

    c |= !!(value & 0xFF00); // 1 => size 2
    c |= (!!(value & 0xFF0000)) << 1; // 2 => size 3
    c |= (!!(value & 0xFF000000)) << 2; // 4 => size 4

    static const int size_table[] = { 1, 2, 3, 3, 4, 4, 4, 4 };
    return size_table[c];
}