用C语言求一个整数的幂的最有效方法是什么?

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

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

当前回答

我的情况有点不同,我试图用一种力量创造一个面具,但我想无论如何我都要分享我找到的解决方案。

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

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

其他回答

一种非常特殊的情况是,当你需要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浮点数的知识,其他幂运算的特殊情况可能会出现。

除了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

如果将发生任何溢出或换行,则返回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.

另一个实现(在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;
    }       
}
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 ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

这是在非对称密码学中对大数进行模求幂的标准方法。