Skip to content

Instantly share code, notes, and snippets.

@Aldizh Aldizh/highest_power

Last active May 1, 2020
Embed
What would you like to do?
Gives you the highest power of x less then provided number n
/*
Problem, find the highest power less than a number n
Iterative solution: O(n)
Logarithmic solution: O(logn)
Bitwise solution: O(logn)
*/
var highestPower = function(n, x) {
var res = 0;
for (var i = n; i >= 1; i--){
var pow = Math.pow(x, i);
if (pow < n) { res = pow; break;}
}
return res;
}
// Log solution
var highestPowerOf2Log = function(n) {
var pow = parseInt(Math.log2(n))
return Math.pow(2, pow);
}
// Using left shift operator
var highestPowerof2Bitwise = function(n) {
var res = 1;
for (var i = 0; i < n; i++){
curr = 1 << i;
if (curr > n) break;
res = curr;
}
return res;
}
console.log('highest power iterative: ', highestPower(73, 2))
console.log('highest power logarithmic: ', highestPowerOf2Log(73))
console.log('highest power bitwise: ', highestPowerof2Bitwise(73))
/*
Left shifting explained:
. 9 (base 10): 00000000000000000000000000001001 (base 2)
--------------------------------
9 << 3 (base 10): 00000000000000000000000001001000 (base 2) = 72 (base 10)
Bitwise shifting any number x to the left by y bits yields x * 2 ^ y.
So e.g.: 9 << 3 translates to: 9 * (2 ^ 3) = 9 * (8) = 72.
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.