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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

Сначала вы можете получить самый старший бит, который совпадает с 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;
}

Ответ 5

Функция поиска позиции первого "1" бита с самой значительной стороны (clzили bsr) обычно представляет собой простую инструкцию CPU (нет необходимости связываться с журналом ₂), поэтому вы можете разделить это на 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 собственный.)

Ответ 6

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

Вы можете найти log _n of x по формуле:

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

Обновление:

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

Ответ 7

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

int count = 0;
while (numbertotest > 0)
{
  numbertotest >>= 8;
  count++;
}

Ответ 8

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

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

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

Ответ 9

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

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

long long limit = 1;
int byteCount;

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

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

Ответ 10

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

nb_bytes = floor (log (x)/log (256)) + 1 если вы используете log2, log2 (256) == 8 так

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

Ответ 11

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

#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

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

Ответ 12

Пол ((log2 (N)/8) + 1) байты

Ответ 13

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

Вариант № 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.

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

Ответ 14

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

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

Ответ 15

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

Ответ 16

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

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

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

Ответ 17

есть много отличных рецептов для таких вещей, как Шон Андерсон "Бит Tweedling Hacks" .

Ответ 18

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

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

Ответ 19

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

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

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

Ответ 20

Это основано на идее 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];
}

Ответ 21

Здесь уже много ответов, но если вы знаете число заблаговременно, в С++ вы можете использовать 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

Ответ 22

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

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