unsigned long long int pow

Question

I have the following power function which operates on integers and it works fine:

int ipow( int base, int exp )
{
    int result = 1;
    while( exp )
    {
        if ( exp & 1 )
        {
            result *= base;
        }
        exp >>= 1;
        base *= base;
    }
    return result;
}

Now I'd like to have a version which allows exp > 32. So I use unsigned long long ints:

unsigned long long int ipow( int base, int exp )
{
    unsigned long long int result = 1ULL;
    while( exp )
    {
        if ( exp & 1 )
        {
            result *= (unsigned long long int)base;
        }
        exp >>= 1;
        base *= base;
    }
    return result;
}

But this second version doesn't seem to work:

unsigned long long int x;
x = ipow( 2, 35 );
printf( "%llu\n", x );

this will output 0.

What's the problem with my unsigned long long int implementation?

Answer 1

Your base variable is too small. Change it to unsigned long long int, like the others, since it holds numbers greater than 2^32.

Answer 2

Section 6.5p4 of the C standard:

Some operators (the unary operator ~, and the binary operators <<, >>, &, ^, and |, collectively described as bitwise operators) are required to have operands that have integer type. These operators yield values that depend on the internal representations of integers, and have implementation-defined and undefined aspects for signed types.

Section 6.5p5 of the C standard:

If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined.

If it seemed like a good idea to use int in this code before, it shouldn't now. Both of these sections are saying that your code isn't as portable as it could be.

Answer 3

For large numbers, it is better to unsigned long long base since in the process of squaring base in my overflow integer type.

unsigned long long int ipow(int base_i, int exp )
    {
      unsigned long long int base = (unsigned long long int) base_i;
      unsigned long long int result = 1ULL;
      while( exp )
      {
          if ( exp & 1 )
          {
              result *= (unsigned long long int)base;
          }
          exp >>= 1;
          base *= base;
      }
      return result;
    }

Then, ipow(2,62) would give the correct answer. ipow(2,63) is already too large (in my system), even though the unsigned long long int should be able to handle approximately 2^64-1.