algorithm - 求幂程序

Question

我正在尝试快速求幂。但是结果似乎并没有产生正确的结果。任何帮助，将不胜感激。编辑:设法解决它感谢所有帮助。

        if (content[i] == '1')
            s1 = (int)(po1 * (Math.pow(po1, 2)));
        else
            s1 = po1 * po1;
        final_result *= temp;

Answer 1

看看这个 Exponation by squaring

每次遇到指数中的 1 位时，您可能希望向右移位并对基数求平方

int pow(int base, int e)
{
    int retVal = 1;
    while (e)
    {
        if (e % 2 == 1)//i.e. last bit of exponent is 1
            retVal *= base;
        e >>= 1; //bitshift exponent to the right.
        base *= base; // square base since we shifted 1 bit in our exponent
    }

    return retVal ;
}

考虑它的一个好方法是你的指数被分解:比如说，6^7(位指数是 1, 1, 1)= 6^1 * 6^2 * 6^4 = 6 * 36 * 36^2 = 6 * 36 * 1296。你的基地总是在摆平自己。