Faster/more concise way to figure out proper size needed to store signed/unsigned ints?

Question

Is there a faster way (possibly bit manipulation?) to find the size needed for an integer of a given value? Here's what I've got:

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

Take the logarithm, base 2, divide it by 8, and round it up to the nearest whole number for unsigned ints. For signed, the same except + 1 before the division by 8.

If you don't have a logarithm function that allows you to specify the base, you can simply convert base via this instead:

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

Example calculation:

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.

This is for arbitrarily large numbers. If you're limiting yourself to only potentially 1,2, or 4 byte results, then just using the switching logic you have is probably the fastest method.

Answer 2

For your uints, it should either be "<= 65535" or "< 65536". Ditto for 2³² but the first one (256) is okay.

I would go for:

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.

This assumes you'll be limiting arguments to 32 bits. If not, add more conditions to hamdle the larger numbers. I don't think your original code would have worked for them anyway since at least one condition is supposed to evaluate true.

Answer 3

As mentioned, the number of bits needed to represent a number in base two can be calculated using logarithms. Such as the following code in 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).

If you are only concerned with word sizes 1,2 and 4, then it is of course nice to check only the few limits. I like to use base 16 for the limits using Erlang's radix notation.

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.

And I assume from your code that you are using two's complement for signed integers. So I map negative numbers over to positive so I can use the same table.

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 4

How about simply:

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