当前位置： 文江博客话题详情

实现基于整数的幂函数 pow(int, int) 的最有效方法

发布于 2024-07-05 11:14:17 字数 108 浏览 14 评论 0原文

在 C 中，将一个整数求另一个整数次方的最有效方法是什么？

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

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

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（20）

无风消散 2024-07-12 11:14:18

我的情况有点不同，我正在尝试从权力创建一个面具，但我想无论如何我都会分享我找到的解决方案。

显然，它只适用于 2 的幂。

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

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;
回复 原文
爱的故事 2024-07-12 11:14:18

如果您在编译时知道指数（并且它是整数），则可以使用模板来展开循环。 这可以变得更高效，但我想在这里演示基本原理：

#include <iostream>

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

我们使用模板专业化终止递归：

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

需要在运行时知道指数，

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

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;
}
回复 原文
涙—继续流 2024-07-12 11:14:17

正如对平方求幂效率的评论的后续。

该方法的优点是它在 log(n) 时间内运行。 例如，如果您要计算一些巨大的数据，例如 x^1048575 (2^20 - 1)，则只需执行循环 20 次，而不是使用朴素方法执行 100 万次以上。

此外，就代码复杂性而言，它比按照普拉莫德的建议尝试找到最佳乘法序列更简单。

编辑：

我想我应该在有人标记我可能溢出之前澄清一下。 这种方法假设您有某种巨大的int库。

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.

回复 原文
我爱人 2024-07-12 11:14:17

迟到了：

下面是一个解决方案，也处理 y < 0 尽可能好。

  1. 它使用 intmax_t 的结果作为最大范围。 没有规定不适合 intmax_t 的答案。
  2. powjii(0, 0) --> powjii(0, 0) --> 1 这是本例的常见结果。

  3. pow(0,negative)，另一个未定义的结果，返回 INTMAX_MAX

    intmax_t powjii(int x, int y) { 
    如果（y<0）{ 
      开关（x）{ 
        案例0： 
          返回 INTMAX_MAX； 
        情况1： 
          返回1； 
        情况1： 
          返回y%2？   -1：1； 
      } 
      返回0； 
    } 
    intmax_t z = 1; 
    intmax_t 基数 = x; 
    为了 （;;） { 
      如果（y％2）{ 
        z *= 基数； 
      } 
      y/=2； 
      如果（y==0）{ 
        休息;  
      } 
      基数 *= 基数； 
    } 
    返回z； 
  }

此代码使用永远循环for(;;)< /code> 以避免其他循环解决方案中常见的最终 base *= base 。 该乘法是 1) 不需要的，2) 可能是 int*int 溢出，即 UB。

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.

回复 原文
鼻尖触碰 2024-07-12 11:14:17
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);
}

是的，它是递归的，但是一个好的优化编译器会优化递归。

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.

回复 原文
吝吻 2024-07-12 11:14:17

考虑负指数的更通用的解决方案

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

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);
}
回复 原文
苦行僧 2024-07-12 11:14:17

除了 Elias 的答案（使用有符号整数实现时会导致未定义的行为，以及使用无符号整数实现时高输入的错误值）之外，

这里是平方求幂的修改版本，它也适用于有符号整数类型，并且不不要给出不正确的值：

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

此函数的注意事项：

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

如果要发生任何溢出或换行，return 0;

我使用了int64_t，但任何宽度（有符号或无符号） ）只需稍作修改即可使用。 但是，如果您需要使用非固定宽度的整数类型，则需要将 SQRT_INT64_MAX 更改为 (int)sqrt(INT_MAX) （在使用int) 或类似的东西，应该优化，但它更难看，而且不是 C 常量表达式。 另外，将 sqrt() 的结果转换为 int 也不是很好，因为在完美平方的情况下，浮点精度很高，但我不知道有任何实现其中 INT_MAX - 或任何类型的最大值 - 是完全平方数，您可以接受。

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.

回复 原文
蒗幽 2024-07-12 11:14:17

请注意，平方求幂并不是最佳方法。 作为适用于所有指数值的通用方法，这可能是您能做的最好的事情，但对于特定的指数值，可能有一个需要更少乘法的更好的序列。

例如，如果您想计算 x^15，则平方求幂的方法将为您提供：

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

这总共是 6 次乘法。

事实证明，这可以通过加法链求幂使用“仅”5次乘法来完成。

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

没有有效的算法来找到最佳的乘法序列。 来自维基百科：

寻找最短加法链的问题无法通过动态规划来解决，因为它不满足最优子结构的假设。 也就是说，将幂分解为较小的幂是不够的，每个较小的幂都被最小化地计算，因为较小幂的加法链可能是相关的（以共享计算）。 例如，在上面 a15 的最短加法链中，a⁶ 的子问题必须计算为 (a3)2，因为 a3 被重复使用（而不是 a6 = a2(a2)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).

回复 原文
独享拥抱 2024-07-12 11:14:17

如果您需要计算 2 的幂。 最快的方法是按功率进行位移位。

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

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)
回复 原文
甜尕妞 2024-07-12 11:14:17

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

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;
}
回复 原文
佼人 2024-07-12 11:14:17

power() 函数适用于仅限整数

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;

}

复杂度 = O(log(exp))

power() 函数适用于负exp和浮动基数。

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 
    }

}

复杂度 = O(log(exp))

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))

回复 原文
花海 2024-07-12 11:14:17

一个极其特殊的情况是，当您需要说 2^(-x 到 y) 时，其中 x, 当然是负数，并且 y 太大而无法对 int 进行移位。 您仍然可以通过拧紧浮子在恒定时间内完成 2^x 。

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

通过使用 double 作为基本类型，您可以获得更多的 2 的幂。
（非常感谢评论者帮助解决这篇文章）。

还有一种可能性是，进一步了解 IEEE 浮点数，其他求幂的特殊情况可能会出现。

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.

回复 原文
偏爱自由 2024-07-12 11:14:17

如果您想获取 2 的整数次幂，最好使用移位选项：

pow(2,5) 可以替换为 1<; <5

这样效率更高。

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.

回复 原文
嘿看小鸭子会跑 2024-07-12 11:14:17
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);
}

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);
}
回复 原文
月隐月明月朦胧 2024-07-12 11:14:17

通过平方求幂。

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

    return result;
}

这是非对称密码学中对大量数字进行模幂运算的标准方法。

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.

回复 原文
青瓷清茶倾城歌 2024-07-12 11:14:17

Swift 中的 O(log N) 解决方案...

// 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 

}

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 

}
回复 原文
蘑菇王子 2024-07-12 11:14:17

另一种实现（用 Java 实现）。 可能不是最有效的解决方案，但迭代次数与指数解决方案相同。

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

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;
    }       
}
回复 原文
风向决定发型 2024-07-12 11:14:17

我使用递归，如果exp是偶数，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);
   }
}

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);
   }
}
回复 原文
滥情哥ㄟ 2024-07-12 11:14:17

我已经实现了记住所有计算功率的算法，然后在需要时使用它们。 例如，x^13 等于 (x^2)^2^2 * x^2^2 * x，其中 x^2^2 是从表中获取的，而不是再次计算。 这基本上是 @Pramod 答案的实现（但在 C# 中）。
需要的乘法次数是 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);
}

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);
}
回复 原文
从来不烧饼 2024-07-12 11:14:17

这是一个用于计算 x ** y 的 O(1) 算法，灵感来自于 此评论。 它适用于 32 位有符号 int。

对于较小的 y 值，它使用平方求幂。 对于较大的 y 值，只有少数 x 值的结果不会溢出。 该实现使用查找表来读取结果而不进行计算。

在溢出时，C 标准允许任何行为，包括崩溃。 然而，我决定对 LUT 索引进行边界检查，以防止内存访问冲突，这可能会令人惊讶且不受欢迎。

伪代码：

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 代码：

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

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;
        }
    }
}
回复 原文
~没有更多了~

关于作者

咿呀咿呀哟

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

留蓝

文章 0 评论 0

18790681156

文章 0 评论 0

zach7772

文章 0 评论 0

Wini

文章 0 评论 0

ayeshaaroy

文章 0 评论 0

初雪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文