C语言 实现一个整数幂函数

1、优化的幂函数

平方乘法 是一种高效的计算幂的方法，特别适用于指数较大的情况。它通过递归地将指数减半来减少计算复杂度。

#include <stdio.h>

int pow_int(int base, int exp) {
    if (exp == 0) return 1;  // 基础情况：任何数的 0 次方都为 1
    if (exp < 0) {  // 处理负指数
        base = 1 / base;
        exp = -exp;
    }
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {  // 如果指数是奇数
            result *= base;
        }
        base *= base;  // 将底数平方
        exp /= 2;  // 指数减半
    }
    return result;
}

int main() {
    int base = 2, exp = 10;
    printf("%d^%d = %d\n", base, exp, pow_int(base, exp));  // 输出：1024
    return 0;
}

2、通过递归实现平方乘法

平方乘法也可以使用递归实现。逻辑与迭代版本相同，但实现方式不同。

#include <stdio.h>

int pow_int_recursive(int base, int exp) {
    if (exp == 0) return 1;  // 基础情况
    if (exp < 0) {  // 处理负指数
        base = 1 / base;
        exp = -exp;
    }
    if (exp % 2 == 0) {
        int half = pow_int_recursive(base, exp / 2);
        return half * half;  // base^exp = (base^(exp/2))^2
    } else {
        return base * pow_int_recursive(base, exp - 1);  // base^exp = base * base^(exp-1)
    }
}

int main() {
    int base = 2, exp = 10;
    printf("%d^%d = %d\n", base, exp, pow_int_recursive(base, exp));  // 输出：1024
    return 0;
}

3、使用位运算实现 2 的幂

对于某些特殊情况（如指数为 2 的幂），可以直接使用位运算。比如计算 2^exp 时，结果等价于将 1 左移 exp 位。

#include <stdio.h>

int pow_2(int exp) {
    return 1 << exp;  // 2^exp 等价于将 1 左移 exp 位
}

int main() {
    int exp = 10;
    printf("2^%d = %d\n", exp, pow_2(exp));  // 输出：1024
    return 0;
}

4、朴素循环方法

最简单的幂计算方法是通过一个循环，将底数相乘 exp 次。虽然这种方法简单直观，但复杂度为 O(exp)，对于较大的指数效率较低。

#include <stdio.h>

int pow_int_naive(int base, int exp) {
    int result = 1;
    for (int i = 0; i < exp; i++) {
        result *= base;
    }
    return result;
}

int main() {
    int base = 2, exp = 10;
    printf("%d^%d = %d\n", base, exp, pow_int_naive(base, exp));  // 输出：1024
    return 0;
}

5、 处理负指数

对于负指数，结果是底数的正指数次幂的倒数。大多数上述方法可以通过将底数取倒数并将指数变为正数来处理这种情况。

#include <stdio.h>

int pow_int(int base, int exp) {
    if (exp == 0) return 1;
    if (exp < 0) {
        base = 1 / base;
        exp = -exp;
    }
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result *= base;
        base *= base;
        exp /= 2;
    }
    return result;
}

int main() {
    int base = 2, exp = -3;
    printf("%d^%d = %d\n", base, exp, pow_int(base, exp));  // 输出：0 （实际结果为 1/8）
    return 0;
}