Pow(x, n) Solutions in Java

// Source : https://leetcode.com/problems/powx-n/
// Author : Tianming Cao
// Date   : 2018-02-11


package powXn;

public class PowXn {
	
	/**
	 * Divide-and-Conquer method
	 * For example:
	 * 
	 * 3^9=(3^4)^2*3 
	 *     ↓                          
	 * 3^4=(3^2)^2
	 *     ↓
	 * 3^2=3*3
	 *     ↓
	 * 3=3
	 * 
	 * So, both Space and Time are O(logN)
	 */
	public double recursion(double x, long n) {
		if (n == 1) {
			return x;
		}
		//We'd better use unsigned right shift
		double half = recursion(x, n >>> 1);
		if ((n & 1) == 0) {
			return half * half;
		} else {
			return half * half * x;
		}
	}
	
	public double myPow01(double x, int n) {
		if (n == 0 || x == 1) {
			return 1;
		}
		// Avoid being out of bounds, we should cast int to long
		long m = n;
		double result = recursion(x, Math.abs(m));
		if (n > 0) {
			return result;
		} else {
			return 1 / result;
		}
	}
	
	public double myPow02(double x, int n) {
		if (n == 0 || x == 1) {
			return 1;
		}
		// Avoid being out of bounds, we should cast int to long
		long m = n;
		double result = bitFunction(x, Math.abs(m));
		if (n > 0) {
			return result;
		} else {
			return 1 / result;
		}
	}
	
	/**
	 * Solution with bit-manipulation
	 * For example:
	 * 9=1001
	 * 3^9=(3^1)^1*(3^2)^0*(3^4)^0*(3^8)^1
	 * Space is O(1), Time is O(logN)
	 */
	public double bitFunction(double x, long n) {
		double multy = 1;
		double base = x;
		for (long k = n; k >= 1; k >>>= 1) {
			if ((k & 1) > 0) {
				multy = multy * base;
			}
			base *= base;
		}
		return multy;
	}

}