The most efficient way to implement an integer based power function pow(int, int)

Question

What is the most efficient way given to raise an integer to the power of another integer in C?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

Copalite

When you say "efficiency," you need to specify efficient in relation to what. Speed? Memory usage? Code size? Maintainability? – Peaceable

Doesn't C have a pow() function? – Darra

yes, but that works on floats or doubles, not on ints – Popcorn

If you're sticking to actual ints (and not some huge-int class), a lot of calls to ipow will overflow. It makes me wonder if there's a clever way to pre-calculate a table and reduce all the non-overflowing combinations to a simple table lookup. This would take more memory than most of the general answers, but perhaps be more efficient in terms of speed. – Mendelssohn

pow() not a safe function – Bronchiole

As pow will easily overflow, either you add checks for that (and thus make it slower), or use unsigned integers and let it wrap around and keep the performance. – Stockpile

Answer 1

Exponentiation by squaring.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

This is the standard method for doing modular exponentiation for huge numbers in asymmetric cryptography.

Becki

With maybe break-out special cases for small exponents known to have better algorithms: turns out the questioner doesn't expect overflow anyway, so these are presumably common. – Jenicejeniece

AKA the "fast exponentiation algorithm". – Darciedarcy

Thanks for the code Elias. I beautified the code a bit for better presentation. – Sensorium

You should probably add a check that "exp" isn't negative. Currently, this function will either give a wrong answer or loop forever. (Depending on whether >>= on a signed int does zero-padding or sign-extension - C compilers are allowed to pick either behaviour). – Almaalmaata

GSL's gsl_sf_pow_int implements this, including the negative case handling: gnu.org/software/gsl/manual/html_node/Power-Function.html – Gussi

I wrote a more optimized version of this, freely downloadable here: gist.github.com/3551590 On my machine it was about 2.5x faster. – Detrimental

@AkhilJain: It's perfectly good C; to make it valid also in Java, replace while (exp) and if (exp & 1) with while (exp != 0) and if ((exp & 1) != 0) respectively. – Jeweljeweler

Your function should probably have unsigned exp, or else handle negative exp properly. – Solstice

This may not be the most optimal solution, see https://mcmap.net/q/99126/-the-most-efficient-way-to-implement-an-integer-based-power-function-pow-int-int – Scully

Anyone explains why this method is better than the easiest way of just multiplying n times? – Split

Do you know the complexity of this algorithm in Big O notation? – Uxorious

it has has Overflow error. Does not work for large numbers e,.g pow(71045970,41535484) – Tevet

@AnushreeAcharjee: That's a domain error anyway. No C implementation can represent that value in an integral type. You'd need a 28*41535484 bit type for that. – Cadency

@ZinanXing Multiplying n times results in more multiplications and is slower. This method saves multiplications by effectively reusing them. E.g., to calculate n^8 the naïve method of n*n*n*n*n*n*n*n uses 7 multiplications. This algorithm instead computes m=n*n, then o=m*m, then p=o*o, where p = n^8, with just three multiplications. With large exponents the difference in performance is significant. – Gulledge

should the return type be changed to long int? – Cymbal

wow; pow(200, 4) takes 25 Clocks on my machine via QueryPerformanceCounter. This implementation rewritten as a macro takes 0-1 clocks! That's literally awesome. – Trengganu

If you care about overflow in base *= base, you should check for it: if (abs(base) > sqrt(INT_MAX)) {break;}. If you don't care about overflow, you should use unsigned base and just let it wrap around. – Stockpile

If this is "the standard method", there must be a standard implementation. Could you link to it? – Syllogistic

Why do you use for (;;) instead of while (true)? – Fillmore

for (;;) is usually considered the more canonical way to do it – Quenchless

Answer 2

Note that exponentiation by squaring is not the most optimal method. It is probably the best you can do as a general method that works for all exponent values, but for a specific exponent value there might be a better sequence that needs fewer multiplications.

For instance, if you want to compute x^15, the method of exponentiation by squaring will give you:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

This is a total of 6 multiplications.

It turns out this can be done using "just" 5 multiplications via addition-chain exponentiation.

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

There are no efficient algorithms to find this optimal sequence of multiplications. From Wikipedia:

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a¹⁵ above, the subproblem for a⁶ must be computed as (a³)² since a³ is re-used (as opposed to, say, a⁶ = a²(a²)², which also requires three multiplies).

Kleinstein

@JeremySalwen: As this answer states, binary exponentiation is not in general the most optimal method. There are no efficient algorithms currently known for finding the minimal sequence of multiplications. – Aria

@EricPostpischil, That depends on your application. Usually we don't need a general algorithm to work for all numbers. See The Art of Computer Programming, Vol. 2: Seminumerical Algorithms – Scully

There's a good exposition of this exact problem in From Mathematics to Generic Programming by Alexander Stepanov and Daniel Rose. This book should be on the shelf of every software practitioner, IMHO. – Lechery

See also en.wikipedia.org/wiki/…. – Agace

This could be optimized for integers because there are well under 255 integer powers that will not cause overflow for 32 bit integers. You could cache the optimal multiplication structure for each int. I imagine the code+data would still be smaller than simply caching all powers... – Waspish

Great answer, thank you ! This can be implemented we templates or constexpr in C++ – Slater

Answer 3

If you need to raise 2 to a power. The fastest way to do so is to bit shift by the power.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

Incorporeal

Is there an elegant way to do this so that 2 ** 0 == 1 ? – Doublethink

@RobSmallshire Maybe 2 ** x = 1 << x (as 1<<0 is 1, you'll have to check if it's in the C std, or if it's platform dependant, but you could do also 2 ** x = x ? (1 << x) : 1 note that 2 ** x has a meaning in C, and that's not power :) – Twist

Answer 4

Here is the method in Java

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

    return result;
}

Diachronic

does not work for large numbes e.g pow(71045970,41535484) – Tevet

@AnushreeAcharjee of course not. Computing such a number would require arbitrary precision arithmetic. – Liquorice

Use BigInteger#modPow or Biginteger#pow for big numbers, appropriate algorithms based on size of arguments are already implemented – Iffy

On the one hand, the question was tagged by the OP as C, so it is clearly a C question. Moreover, these kind of microoptimizations are not usually done in such high level languages (performance is not what you're after, if you use Java, I guess). On the other hand, if this question is high in search engines, it might be interesting to expand it to other languages too. So, never mind my old comment :) – Stockpile

@AnushreeAcharjee : yeah youve also forgotten that 71045970 ^ 41535484 has 326mn digits in decimal – Hobnob

Answer 5

An extremely specialized case is, when you need say 2^(-x to the y), where x, is of course is negative and y is too large to do shifting on an int. You can still do 2^x in constant time by screwing with a float.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

You can get more powers of 2 by using a double as the base type. (Thanks a lot to commenters for helping to square this post away).

There's also the possibility that learning more about IEEE floats, other special cases of exponentiation might present themselves.

Copalite

Nifty solution, but unsigend?? – Redfish

An IEEE float is base x 2 ^ exp, changing the exponent value won't lead to anything else than a multiplication by a power of two, and chances are high it will denormalize the float ... your solution is wrong IMHO – Whitefish

You are all correct, I misremembered that my solution was originally written, oh so long ago, for powers of 2 explicitly. I've rewritten my answer to be a special case solution to the problem. – Copalite

Firstly, the code is broken as quoted, and requires editing to get it to compile. Secondly the code is broken on a core2d using gcc. see this dump Perhaps I did something wrong. I however do not think this will work, since the IEEE float exponent is base 10. – Bohlin

Base 10? Uh no, it's base 2, unless you meant 10 in binary :) – Whitefish

Doesn't seem to work for powers of 2 either... I would like to see this in action, can some one spot my mistake in my previous pastebin? Also, embrassingly, I made an error in my previous comment, and said base 10 when I really wanted base 2 ;) – Bohlin

You still should be multiplying the exponents, not adding them. And look into CPU-specific implementations. For instance on x86, bsr to find the hibit will be no slower than an int->double conversion and probably faster. – Jenicejeniece

Just noticed that you're now calculating pow(2,n). This can be done in a single CPU instruction on most platforms with 1 << n, except that you must range-check n first, since 1 << 32 is undefined behaviour. – Jenicejeniece

Thanks for humbling me, seriously. I completely misremembered something I did long ago, and was corrected. Thank god too, because someone might have tried to run with my solution! If you voted me up, feel completely free to undo it – Copalite

-1 useless; exponentiating 2 is more easily performed by bitshifting. Also bitfields have unspecified order within the larger type so this code is not portable even across compilers with the same (IEEE) float implementation. Further, you need signed char if you claim your comment is correct, as the signedness of char is unspecified. – Kenosis

Answer 6

power() function to work for Integers Only

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

Complexity = O(log(exp))

power() function to work for negative exp and float base.

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

Complexity = O(log(exp))

Onstage

How is this different from the answers of Abhijit Gaikwad and chux? Please argue the use of float in the second code block presented (consider showing how power(2.0, -3) gets computed). – Mertz

@Mertz I have mentioned some comment. may be that can resolve your query – Onstage

GNU Scientific Library already has your second function: gnu.org/software/gsl/manual/html_node/Small-integer-powers.html – Stockpile

@Onstage could you please explain negative exp and float base solution? why we use temp, separate exp by 2 and check exp (even/odd)? thanks! – Samira

Answer 7

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}

Kapok

Not my vote, but pow(1, -1) doesn't leave the range of int despite a negative exponent. Now that one works by accident, as does pow(-1, -1). – Cadency

The only negative exponent that may not make you leave the range of int is -1. And it only works if base is 1 or -1. So there are only two pairs (base,exp) with exp<0 that would not lead to non integer powers. Although I'm a matematician and I like quantifiers, I think in this case, in practice, it's ok to say that a negative exponent makes you leave the integer realm... – Mischief

Answer 8

If you want to get the value of an integer for 2 raised to the power of something it is always better to use the shift option:

pow(2,5) can be replaced by 1<<5

This is much more efficient.

Copulate

Answer 9

Just as a follow up to comments on the efficiency of exponentiation by squaring.

The advantage of that approach is that it runs in log(n) time. For example, if you were going to calculate something huge, such as x^1048575 (2^20 - 1), you only have to go thru the loop 20 times, not 1 million+ using the naive approach.

Also, in terms of code complexity, it is simpler than trying to find the most optimal sequence of multiplications, a la Pramod's suggestion.

Edit:

I guess I should clarify before someone tags me for the potential for overflow. This approach assumes that you have some sort of hugeint library.

Hillegass

Answer 10

Late to the party:

Below is a solution that also deals with y < 0 as best as it can.

1. It uses a result of intmax_t for maximum range. There is no provision for answers that do not fit in intmax_t.
2. powjii(0, 0) --> 1 which is a common result for this case.

3. pow(0,negative), another undefined result, returns INTMAX_MAX

   intmax_t powjii(int x, int y) {
     if (y < 0) {
       switch (x) {
         case 0:
           return INTMAX_MAX;
         case 1:
           return 1;
         case -1:
           return y % 2 ? -1 : 1;
       }
       return 0;
     }
     intmax_t z = 1;
     intmax_t base = x;
     for (;;) {
       if (y % 2) {
         z *= base;
       }
       y /= 2;
       if (y == 0) {
         break; 
       }
       base *= base;
     }
     return z;
   }
   

This code uses a forever loop for(;;) to avoid the final base *= base common in other looped solutions. That multiplication is 1) not needed and 2) could be int*int overflow which is UB.

Gelatinoid

powjii(INT_MAX, 63) causes UB in base *= base. Consider checking that you can multiply, or move to unsigned and let it wrap around. – Stockpile

There is no reason to have exp be signed. It complicates the code because of the odd situation where (-1) ** (-N) is valid, and any abs(base) > 1 will be 0 for negative values of exp, so it is better to have it unsigned and save that code. – Stockpile

@CacahueteFrito True that y as signed is not really needed and brings the complications you commented on, yet OP's request was specific pow(int, int). Thus those good comments belong with the OP's question. As OP has not specified what to do on overflow, a well defined wrong answer is only marginally better than UB. Given "most efficient way", I doubt OP cares about OF. – Gelatinoid

Answer 11

int pow(int const x, unsigned const e) noexcept
{
  return !e ? 1 : 1 == e ? x : (e % 2 ? x : 1) * pow(x * x, e / 2);
  //return !e ? 1 : 1 == e ? x : (((x ^ 1) & -(e % 2)) ^ 1) * pow(x * x, e / 2);
}

Yes, it's recursive, but a good optimizing compiler will optimize recursion away.

Nucleolus

Clang does optimize the tail recursion, but gcc doesn't unless you replace order of multiplication i.e. (e % 2 ? x : 1) * pow(x * x, e / 2) godbolt.org/z/EoWbfx5nc – Simonne

@Simonne I did notice gcc was struggling, but I don't mind, since I'm using this function as a constexpr function. – Nucleolus

Answer 12

more generic solution considering negative exponenet

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

Interrelation

integer division results in an integer, so your negative exponent could be a lot more efficient since it'll only return 0, 1, or -1... – Stalactite

pow(i, INT_MIN) could be an infinite loop. – Gelatinoid

@chux: It could format your harddisk: integer overflow is UB. – Cadency

@Cadency pow(i, INT_MIN) is not integer overflow. The assignment of that result to temp certainly may overflow, potential causing the end of time, but I'll settle for a seemingly random value. :-) – Gelatinoid

Answer 13

In addition to the answer by Elias, which causes Undefined Behaviour when implemented with signed integers, and incorrect values for high input when implemented with unsigned integers,

here is a modified version of the Exponentiation by Squaring that also works with signed integer types, and doesn't give incorrect values:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

Considerations for this function:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

If any overflow or wrapping is going to take place, return 0;

I used int64_t, but any width (signed or unsigned) can be used with little modification. However, if you need to use a non-fixed-width integer type, you will need to change SQRT_INT64_MAX by (int)sqrt(INT_MAX) (in the case of using int) or something similar, which should be optimized, but it is uglier, and not a C constant expression. Also casting the result of sqrt() to an int is not very good because of floating point precission in case of a perfect square, but as I don't know of any implementation where INT_MAX -or the maximum of any type- is a perfect square, you can live with that.

Stockpile

Answer 14

The O(log N) solution in Swift...

// Time complexity is O(log N)
func power(_ base: Int, _ exp: Int) -> Int { 

    // 1. If the exponent is 1 then return the number (e.g a^1 == a)
    //Time complexity O(1)
    if exp == 1 { 
        return base
    }

    // 2. Calculate the value of the number raised to half of the exponent. This will be used to calculate the final answer by squaring the result (e.g a^2n == (a^n)^2 == a^n * a^n). The idea is that we can do half the amount of work by obtaining a^n and multiplying the result by itself to get a^2n
    //Time complexity O(log N)
    let tempVal = power(base, exp/2) 

    // 3. If the exponent was odd then decompose the result in such a way that it allows you to divide the exponent in two (e.g. a^(2n+1) == a^1 * a^2n == a^1 * a^n * a^n). If the eponent is even then the result must be the base raised to half the exponent squared (e.g. a^2n == a^n * a^n = (a^n)^2).
    //Time complexity O(1)
    return (exp % 2 == 1 ? base : 1) * tempVal * tempVal 

}

Natalee

Answer 15

One more implementation (in Java). May not be most efficient solution but # of iterations is same as that of Exponential solution.

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

    if(exp % 2 == 0){
        long half = pow(base, exp/2);
        return half * half;
    }else{
        long half = pow(base, (exp -1)/2);
        return base * half * half;
    }       
}

Contemptuous

Not a Java question! – Stockpile

Answer 16

I use recursive, if the exp is even,5^10 =25^5.

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

Bijugate

Answer 17

I have implemented algorithm that memorizes all computed powers and then uses them when need. So for example x^13 is equal to (x^2)^2^2 * x^2^2 * x where x^2^2 it taken from the table instead of computing it once again. This is basically implementation of @Pramod answer (but in C#). The number of multiplication needed is Ceil(Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

Zarathustra

public? 2 functions named the same? This is a C question. – Stockpile

Answer 18

Here is a O(1) algorithm for calculating x ** y, inspired by this comment. It works for 32-bit signed int.

For small values of y, it uses exponentiation by squaring. For large values of y, there are only a few values of x where the result doesn't overflow. This implementation uses a lookup table to read the result without calculating.

On overflow, the C standard permits any behavior, including crash. However, I decided to do bound-checking on LUT indices to prevent memory access violation, which could be surprising and undesirable.

Pseudo-code:

If `x` is between -2 and 2, use special-case formulas.
Otherwise, if `y` is between 0 and 8, use special-case formulas.
Otherwise:
    Set x = abs(x); remember if x was negative
    If x <= 10 and y <= 19:
        Load precomputed result from a lookup table
    Otherwise:
        Set result to 0 (overflow)
    If x was negative and y is odd, negate the result

C code:

#define POW9(x) x * x * x * x * x * x * x * x * x
#define POW10(x) POW9(x) * x
#define POW11(x) POW10(x) * x
#define POW12(x) POW11(x) * x
#define POW13(x) POW12(x) * x
#define POW14(x) POW13(x) * x
#define POW15(x) POW14(x) * x
#define POW16(x) POW15(x) * x
#define POW17(x) POW16(x) * x
#define POW18(x) POW17(x) * x
#define POW19(x) POW18(x) * x

int mypow(int x, unsigned y)
{
    static int table[8][11] = {
        {POW9(3), POW10(3), POW11(3), POW12(3), POW13(3), POW14(3), POW15(3), POW16(3), POW17(3), POW18(3), POW19(3)},
        {POW9(4), POW10(4), POW11(4), POW12(4), POW13(4), POW14(4), POW15(4), 0, 0, 0, 0},
        {POW9(5), POW10(5), POW11(5), POW12(5), POW13(5), 0, 0, 0, 0, 0, 0},
        {POW9(6), POW10(6), POW11(6), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(7), POW10(7), POW11(7), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(8), POW10(8), 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(9), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(10), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    int is_neg;
    int r;

    switch (x)
    {
    case 0:
        return y == 0 ? 1 : 0;
    case 1:
        return 1;
    case -1:
        return y % 2 == 0 ? 1 : -1;
    case 2:
        return 1 << y;
    case -2:
        return (y % 2 == 0 ? 1 : -1) << y;
    default:
        switch (y)
        {
        case 0:
            return 1;
        case 1:
            return x;
        case 2:
            return x * x;
        case 3:
            return x * x * x;
        case 4:
            r = x * x;
            return r * r;
        case 5:
            r = x * x;
            return r * r * x;
        case 6:
            r = x * x;
            return r * r * r;
        case 7:
            r = x * x;
            return r * r * r * x;
        case 8:
            r = x * x;
            r = r * r;
            return r * r;
        default:
            is_neg = x < 0;
            if (is_neg)
                x = -x;
            if (x <= 10 && y <= 19)
                r = table[x - 3][y - 9];
            else
                r = 0;
            if (is_neg && y % 2 == 1)
                r = -r;
            return r;
        }
    }
}

Underworld

Answer 19

My case is a little different, I'm trying to create a mask from a power, but I thought I'd share the solution I found anyway.

Obviously, it only works for powers of 2.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;

Coonhound

I tried that, it doesn't work for 64 bit, it's shifted off never to return, and in this specific case, I'm trying to set all bits lower than X, inclusive. – Coonhound

Was that for 1 << 64 ? That's an overflow. The largest integer is just below that: (1 << 64) - 1. – Quorum

1 << 64 == 0, that's why. Maybe your representation is best for your app. I prefer stuff that can be put in a macro, without an extra variable, like #define MASK(e) (((e) >= 64) ? -1 :( (1 << (e)) - 1)), so that can be computed at compile time – Quorum

Yes, i know what an overflow is. Just because i didm't use that word isn't an invitation to be needlessly condescending. As i said, this works for me and it took a bit of effort to discover hence sharing it. It's that simple. – Coonhound

I'm sorry if I offended you. I truly didn't mean to. – Quorum

1) The return value is NOT a power of 2. 2) If you want to create a 64 bit mask that has n ones to the right, it is easier: uint64_t mask = (UINT64_C(1) << n) - 1; – Stockpile

@CacahueteFrito Yeah, I know. ((1 << X) - 1) is what I do to create LSBit masks, for MSBit it's more complicated. – Coonhound

@Coonhound Also you should use an explicit macro for the type of the 1. If not, you may have overflow. – Stockpile

@Coonhound For n MSbits in a 64 bit mask: (~(((uint64_t)UINT64_MAX) >> n)). You answer is not related to pow. By the way, UINT64_C in my other comment should be replaced by (uint64_t). – Stockpile

Answer 20

In case you know the exponent (and it is an integer) at compile-time, you can use templates to unroll the loop. This can be made more efficient, but I wanted to demonstrate the basic principle here:

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

We terminate the recursion using a template specialization:

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

The exponent needs to be known at runtime,

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}

Acker

This is clearly not a C++ question. (c != c++) == 1 – Stockpile