Skip to content

Instantly share code, notes, and snippets.

@ag8023
Created February 6, 2025 18:42
Show Gist options
  • Save ag8023/694baa0c7bb7b2b0bbb11f9119df1f57 to your computer and use it in GitHub Desktop.
Save ag8023/694baa0c7bb7b2b0bbb11f9119df1f57 to your computer and use it in GitHub Desktop.
Calculate Power(binary exponentiation)
class Solution {
public:
double myPow(double x, int n) {
// double soln = x; // initialize to x
// if(n == 0 || x == 1)
// return 1;
// if ( x == -1 && n%2 == 0)
// return 1;
// if ( x == -1 && n%2 != 0)
// return -1;
// for(int i = 1; i < abs(n) ; i++){
// soln *= x;
// }
// if(n > 0)
// return soln;
// else
// return 1.0/soln;
//---------------------------------------------------------------------------------------------
// if(n < 0){
// x = 1/x;
// n = abs(n);
// }
// if(n == 0){
// return 1;
// }
// if(n%2 != 0){
// return x*myPow(x, n-1);
// } else{
// return myPow(x*x, n/2);
// }
//--------------------------------------------------------------------------------------------------
// using binary exponentiation
if(n == 0 || x == 1){
return 1.0;
}
if(x == 0){
return 0.0;
}
if(x == -1 && n%2 == 0){
return 1.0;
}
if(x == -1 && n%2 != 0){
return -1.0;
}
long binform = n;
if(n < 0) {
x = 1/x; // for negative power, take reciprocal
binform = -binform;
}
double ans = 1;
while(binform > 0){
if(binform % 2 == 1){
ans *= x;
}
x *= x;
binform/=2;
}
return ans;
}
};
// 2 * myPow(2, 2)
// 2 * myPow(4, 1)
// 2 *(4 * myPow(4, 0)) = 2 *(4 * 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment