Question

How to implement an integer-based power function pow(int, int) in C

Answer 1

#include <stdio.h>
 
int intpow(int base, int exp) {
    int power = 1;
    
    while (1) {
        if (exp & 1)
            power *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }
 
    return power;
}
 
int main()
{
    printf("%d\n", intpow(2, 3));  // 8
    printf("%d\n", intpow(3, 3));  // 27
    printf("%d\n", intpow(3, 2));  // 9
    printf("%d\n", intpow(2, 2));  // 4
    printf("%d\n", intpow(5, 2));  // 25
    printf("%d\n", intpow(-2, 4)); // 16
     
    return 0;
}

 
 
/*
run:
  
8
27
9
4
25
16
 
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>
#include <stdlib.h>

/*
    Integer power function: intpow(base, exp)

    - Computes base^exp using an efficient method known as exponentiation by squaring.
      This reduces the number of multiplications and runs in logarithmic time.

    - Negative exponents are not supported because the result would not be an integer.
      The function checks for this and stops early.

    - The algorithm works by:
        • Checking each bit of the exponent.
        • Multiplying the result when the current bit is set.
        • Squaring the base at each step.
        • Shifting the exponent right until it reaches zero.

    - Uses wider intermediate types to reduce overflow risk.
*/

int intpow(int base, int exp) {
    if (exp < 0) {
        fprintf(stderr, "intpow: negative exponent not supported\n");
        exit(EXIT_FAILURE);
    }

    if (exp == 0) {
        return 1;
    }

    long long result = 1;
    long long current = base;

    while (exp > 0) {
        if (exp & 1) {
            result *= current;
        }

        current *= current;
        exp >>= 1;
    }

    return (int)result;
}

/*
    Test main
*/
int main() {
    printf("%d\n", intpow(2, 3));  // 8
    printf("%d\n", intpow(3, 3));  // 27
    printf("%d\n", intpow(3, 2));  // 9
    printf("%d\n", intpow(2, 2));  // 4
    printf("%d\n", intpow(5, 2));  // 25
    printf("%d\n", intpow(-2, 4)); // 16

    return 0;
}



/*
run:

8
27
9
4
25
16

*/

 

70+ SQL courses for beginners and professionals