package Maths;

public class BinaryPow {
 /**
 * Calculate a^p using binary exponentiation
 * [Binary-Exponentiation](https://cp-algorithms.com/algebra/binary-exp.html)
 *
 * @param a the base for exponentiation
 * @param p the exponent - must be greater than 0
 * @return a^p
 */
 public static int binPow(int a, int p) {
 int res = 1;
 while (p > 0) {
 if ((p & 1) == 1) {
 res = res * a;
 }
 a = a * a;
 p >>>= 1;
 }
 return res;
 }

 /**
 * Function for testing binary exponentiation
 *
 * @param a the base
 * @param p the exponent
 */
 public static void test(int a, int p) {
 int res = binPow(a, p);
 assert res == (int) Math.pow(a, p) : "Incorrect Implementation";
 System.out.println(a + "^" + p + ": " + res);
 }

 /**
 * Main Function to call tests
 *
 * @param args System Line Arguments
 */
 public static void main(String[] args) {
 // prints 2^15: 32768
 test(2, 15);

 // prints 3^9: 19683
 test(3, 9);
 }
}