Более быстрый / более краткий способ определить правильный размер, необходимый для хранения подписанных / неподписанных целых?

Question

Есть ли более быстрый способ (возможно, битовая манипуляция?), Чтобы найти размер, необходимый для целого числа данного значения? Вот что у меня есть:

uint_length(Value) ->
if Value < 256 -> 1;
   Value < 65535 -> 2;
   Value < 4294967295 -> 4
end.

sint_length(Value) ->
if Value < 128 andalso Value >= 0 -> 1;
   Value < 32767 andalso Value >= 0 -> 2;
   Value < 2147483647 andalso Value >= 0 -> 4;
   Value > -128 -> 1;
   Value > -32767 -> 2;
   Value > -2147483647 -> 4
end.

Answer 1

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

bits(0) -> 
  1;
bits(X) when is_number(X), X < 0 ->
  1 + bits(erlang:abs(X));
bits(X) when is_number(X) ->
  erlang:trunc(math:log(X) / math:log(2) + 1).

Если вас интересуют только размеры слов 1,2 и 4, то, конечно, приятно проверить только несколько ограничений. Мне нравится использовать базу 16 для пределов, используя радикальную нотацию Эрланга.

unsigned_wordsize(X) when is_integer(X), X >= 0 ->
  case X of
    _ when X =< 16#000000ff -> 1;
    _ when X =< 16#0000ffff -> 2;
    _ when X =< 16#ffffffff -> 4
  end.

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

signed_wordsize(X) when is_integer(X), X < 0 ->
  signed_wordsize(-(X+1));
signed_wordsize(X) when is_integer(X) ->
  case X of
    _ when X =< 16#0000007f -> 1;
    _ when X =< 16#00007fff -> 2;
    _ when X =< 16#7fffffff -> 4
  end.

Answer 2

Для ваших мнений оно должно быть либо "<= 65535", либо "< 65536". То же самое для 2 ³² , но первый (256) в порядке.

Я бы пошел на:

uint_length(Value) ->
if Value <=   255 -> 1;
   Value <= 65535 -> 2;
   true           -> 4
end.

sint_length(Value) ->
if Value <=   127 andalso Value >=   -128 -> 1;
   Value <= 32767 andalso Value >= -32768 -> 2;
   true                                   -> 4
end.

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

Answer 3

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

Если у вас нет функции логарифма, которая позволяет указывать базу, вы можете просто преобразовать базу с помощью этого:

log_base_2(value) = log(value)/log(2) # if you have log() for log-base10
log_base_2(value) = ln(value)/ln(2) # if you have ln() for log-base-e

Пример расчета:

To store 368:

ln(368) ~= 5.908
ln(368)/ln(2) ~= 8.524
( ln(368)/ln(2) ) / 8 ~= 1.065

Rounding up gives 1.065 -> 2, thus we need 2 bytes to store 368 as an unsigned integer.

Это для сколь угодно больших чисел. Если вы ограничиваете себя только потенциально 1,2 или 4-байтовыми результатами, то просто использование имеющейся у вас логики переключения, вероятно, самый быстрый метод.

Answer 4

Как насчет просто:

nr_bytes(Value) ->
  if Value < 256 -> 1;
     true        -> 1 + nr_bytes(Value bsr 8)
  end.