Implement Exponentiation or Power function using Bitwise Operator

Calculating the n-th power of a number can also be efficiently done with a fast technique called exponentiation by squaring.

We know, a^l = a ^ (m + n) = a^m * a^n. For eg. a10 = a8+2 = a8 * a2.

Also, a*a = a^2, a^2*a^2 = a^4 and so on.

The basic concept relies on the following recursion

$x^y=\begin{cases} x , ( x^{2})^{\frac{y - 1}{2}}, & \mbox{if } y \mbox{ is odd} \ (x^{2})^{\frac{y}{2}} , & \mbox{if } y \mbox{ is even}. \end{cases}$

N = 9 = 2^3 + 2^0 = 1001 in binary. Then:

x^9 = x^(2^3) * x^(2^0)

We can see that every time we encounter a 1 in the binary representation of N, we need to multiply the answer with x^(2^i) where i is the ith bit of the exponent. Thus, we can keep a running total of repeatedly squaring x - (x, x^2, x^4, x^8, etc) and multiply it by the answer when we see a 1.

A recursive approach naturally follows

int pow(int x, int y) {  
	if (y == 0)  
		return 1;  
	else  
		return pow(x*x, y >> 1) * ((y % 2 != 0) ? x : 1);  
}

The same iterative version might be more readable though

int pow(int x, int y) {  
  
	int result = 1;  
	while (y != 0) {  
  
		if (y % 2 != 0)  
			result *= x;  
  
		x *= x;  
		y >>= 1;  
	}  
  
	return result;  
}

Regarding the fact that we used the modulo operator to get the remainder in the snippets above, this can be implemented in several trivial ways, e.g. by just looping over the divisor until it is greater than the dividend and returning their difference and keeping in mind

$x \pmod y = -x \pmod y = x \pmod{-y} \ x \pmod y = -(-x \pmod{-y})$

as particular cases if negative integer support needs to be implemented.

To handle the case where N=INTEGER_MIN we use a long (64-bit) variable. Below is solution:

public double pow(double x, int n) {
	double ans = 1;
	long absN = Math.Abs((long)n);
	while(absN > 0) {
		// odd bit check
		if((absN&1)==1) ans *= x;
		absN >>= 1;
		x *= x;
	}
	return n < 0 ?  1/ans : ans;
}