algorithm to figure out how many bytes are required to hold an int_问答_开发者

sorry for the stupid question, but how would I go about figuring out, mathematically or using c++, how man开发者_开发百科y bytes it would take to store an integer.

If you mean from an information theory point of view, then the easy answer is:

log(number) / log(2)

(It doesn't matter if those are natural, binary, or common logarithms, because of the division by log(2), which calculates the logarithm with base 2.)

This reports the number of bits necessary to store your number.

If you're interested in how much memory is required for the efficient or usual encoding of your number in a specific language or environment, you'll need to do some research. :)

The typical C and C++ ranges for integers are:

 char    1 byte
 short   2 bytes
 int     4 bytes
 long    8 bytes

If you're interested in arbitrary-sized integers, special libraries are available, and every library will have its own internal storage mechanism, but they'll typically store numbers via 4- or 8- byte chunks up to the size of the number.

You could find the first power of 2 that's larger than your number, and divide that power by 8, then round the number up to the nearest integer. So for 1000, the power of 2 is 1024 or 2^10; divide 10 by 8 to get 1.25, and round up to 2. You need two bytes to hold 1000!

If you mean "how large is an int" then sizeof(int) is the answer.

If you mean "how small a type can I use to store values of this magnitude" then that's a bit more complex. If you already have the value in integer form, then presumably it fits in 4, 3, 2, or 1 bytes. For unsigned values, if it's 16777216 or over you need 4 bytes, 65536-16777216 requires 3 bytes, 256-65535 needs 2, and 0-255 fits in 1 byte. The formula for this comes from the fact that each byte can hold 8 bits, and each bit holds 2 digits, so 1 byte holds 2^8 values, ie. 256 (but starting at 0, so 0-255). 2 bytes therefore holds 2^16 values, ie. 65536, and so on.

You can generalise that beyond the normal 4 bytes used for a typical int if you like. If you need to accommodate signed integers as well as unsigned, bear in mind that 1 bit is effectively used to store whether it is positive or negative, so the magnitude is 1 power of 2 less.

You can calculate the number of bits you need iteratively from an integer by dividing it by two and discarding the remainder. Each division you can make and still have a non-zero value means you have one more bit of data in use - and every 8 bits you're using means 1 byte.

A quick way of calculating this is to use the shift right function and compare the result against zero.

int value = 23534; // or whatever
int bits = 0;

while (value)
{
    value >> 1;
    ++bits;
}
std::cout << "Bits used = " << bits << std::endl;
std::cout << "Bytes used = " << (bits / 8) + 1 << std::endl;

This is basically the same question as "how many binary digits would it take to store a number x?" All you need is the logarithm.

A n-bit integer can store numbers up to 2ⁿ-1. So, given a number x, ceil(log₂ x) gets you the number of digits you need.

It's exactly the same thing as figuring out how many decimal digits you need to write a number by hand. For example, log₁₀ 123456 = 5.09151220... , so ceil( log₁₀(123456) ) = 6, six digits.

Since nobody put up the simplest code that works yet, I mind as well do it:

unsigned int get_number_of_bytes_needed(unsigned int N) {
  unsigned int bytes = 0;
  while(N) { 
    N >>= 8;
    ++bytes;
  };
  return bytes;
};

assuming sizeof(long int) = 4.

int nbytes( long int x )
{
  unsigned long int n = (unsigned long int) x;

  if (n <= 0xFFFF)
  {
    if (n <= 0xFF) return 1;
    else return 2;
  }
  else
  {
    if (n <= 0xFFFFFF) return 3;
    else return 4;
  }
}

The shortest code way to do this is as follows:

int bytes = (int)Math.Log(num, 256) + 1;

The code is small enough to be inlined, which helps offset the "slow" FP code. Also, there are no branches, which can be expensive.

Try this code:

// works for num >= 0
int numberOfBytesForNumber(int num) {
   if (num < 0)
      return 0;
   else if (num == 0)
      return 1;
   else if (num > 0) {
      int n = 0;
      while (num != 0) {
        num >>= 8;
        n++;
      }
      return n;
   }
}

/**
 * assumes i is non-negative.
 * note that this returns 0 for 0, when perhaps it should be special cased?
 */
int numberOfBytesForNumber(int i) {
    int bytes = 0;
    int div = 1;
    while(i / div) {
        bytes++;
        div *= 256;
    }
    if(i % 8 == 0) return bytes;
    return bytes + 1;
}

This code runs at 447 million tests / sec on my laptop where i = 1 to 1E9. i is a signed int:

n = (i > 0xffffff || i < 0) ? 4 : (i < 0xffff) ? (i < 0xff) ? 1 : 2 : 3;

Python example: no logs or exponents, just bit shift.

Note: 0 counts as 0 bits and only positive ints are valid.

def bits(num):
    """Return the number of bits required to hold a int value."""
    if not isinstance(num, int):
        raise TypeError("Argument must be of type int.")
    if num < 0:
        raise ValueError("Argument cannot be less than 0.")

    for i in count(start=0):
        if num == 0:
            return i
        num = num >> 1