Finding the maximum number of bits for a specific integer

Question

Alright guys, I am completely stuck on this little problem that I spent hours trying to research and figure out. Basically all I have to do is find the maximum number of bits(using a byte as limitation) for an integer. An example of what I am trying to do is: int 5 would show up as 8 because in a byte it is stored as 0000 0101. Everything that is up to and including 255 should output 8. once you get to 256, it should output 16 as it will be stored as 0001 0000 0000 . I could use if statements but is there an easier way of doing this using logs?

All I have so far is:

    int x = 5;
    int len = (Integer.toString(x)).length();
    double bits = Math.ceil(len*(Math.log(10)/Math.log(2)));
    System.out.println(bits);

Answer 1

A very simple approach:

final double DIVISOR = Math.log(256);

int x = 5;
double bytes = Math.log(x) / DIVISOR;
int bits = (int) Math.ceil(bytes) * 8;

This computes the number of bytes for the number (including partial bytes) by computing the number of digits in base 256. This uses two tricks:

• The number of digits of a number x in base n is given by log_n(x).
• log_n(x) is equivalent to log_m(x)/log_m(n) for any m.

It then rounds that result up (to deal with any partial bytes), and multiplies by eight to get the number of bits.

Please note, however, that this is not necessarily a very efficient approach. There are more efficient methods possible that use bit manipulation, but which are probably a little harder to understand. This method, at least, seems similar to what you've already tried.