How to determine how many bytes an integer needs?

Question

Use this:

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

This assumes that x contains your (positive) value.

Note that zero will be declared encodable as no byte at all. Also, most variable-size encodings need some length field or terminator to know where encoding stops in a file or stream (usually, when you encode an integer and mind about size, then there is more than one integer in your encoded object).

You need just two simple ifs if you are interested on the common sizes only. Consider this (assuming that you actually have unsigned values):

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

Should you need to test for other sizes, choosing a middle point and then doing nested tests will keep the number of tests very low in any case. However, in that case making the testing a recursive function might be a better option, to keep the code simple. A decent compiler will optimize away the recursive calls so that the resulting code is still just as fast.

Assuming a byte is 8 bits, to represent an integer x you need [log2(x) / 8] + 1 bytes where [x] = floor(x).

Ok, I see now that the byte sizes aren't necessarily a power of two. Consider the byte sizes b. The formula is still [log2(x) / b] + 1.

Now, to calculate the log, either use lookup tables (best way speed-wise) or use binary search, which is also very fast for integers.

The function to find the position of the first '1' bit from the most significant side (clz or bsr) is usually a simple CPU instruction (no need to mess with log₂), so you could divide that by 8 to get the number of bytes needed. In gcc, there's __builtin_clz for this task:

#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;
}

(On MSVC you would use the _BitScanReverse intrinsic.)