CODEWITHSUNDEEP
c++algorithmmath
Anonymous
Anonymous

Reputation: 81

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 many bytes it would take to store an integer.

Upvotes: 8

Views: 14325

Answers (11)

Juan Molina Riddell
Juan Molina Riddell

Reputation: 15

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

Upvotes: 0

IamIC
IamIC

Reputation: 18259

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;

Upvotes: 0

IamIC
IamIC

Reputation: 18259

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.

Upvotes: 1

Kylotan
Kylotan

Reputation: 18449

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;

Upvotes: 3

Mikael Persson
Mikael Persson

Reputation: 18572

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

Upvotes: 2

corsiKa
corsiKa

Reputation: 82589

/**
 * 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;
}

Upvotes: 0

yasouser
yasouser

Reputation: 5177

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

Upvotes: 1

anubhava
anubhava

Reputation: 785541

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

Upvotes: 0

sarnold
sarnold

Reputation: 104080

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.

Upvotes: 11

Crashworks
Crashworks

Reputation: 41444

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 2n-1. So, given a number x, ceil(log2 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, log10 123456 = 5.09151220... , so ceil( log10(123456) ) = 6, six digits.

Upvotes: 2

Ernest Friedman-Hill
Ernest Friedman-Hill

Reputation: 81704

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!

Upvotes: 9

Related Questions