I need to develop an algorithm in VisuAlg where I enter a number and it tells me whether it is a power of 2 or not. What strategies can I use?
I need to develop an algorithm in VisuAlg where I enter a number and it tells me whether it is a power of 2 or not. What strategies can I use?
For this case just apply a single formula :
Log Value / Log 2 .
If the result is a integer then the reported value is based on the power of 2 .
MATHEMATICAL EXPLANATION
We have 2 power of x is equal to and , where y is the number you wants to know if the base is equal to 2 , and x is the 2 power that will result in and .
By the properties of mathematics, and in particular that of logarithms, the solution below follows.
Attention: Do not round values as shown in this example, otherwise the result will not be an integer value !!!
So without rounding values , check that the result does not have decimal places ( integer ), and when not displaying, you'll know that this value is formed by base power 2 . Good luck!
Successively divide your x number by 2.
If the remainder is always 0 and you reach quotient 1, then x is a power of 2.
Example:
8192/2 = 4096
4096/2 = 2048
2048/2 = 1024
1024/2 = 512
512/2 = 256
256/2 = 128
128/2 = 64
64/2 = 32
32/2 = 16
16/2 = 8
8/2 = 4
4/2 = 2
2/2 = 1
8192 is a power of 2.
The most efficient way is to check if the number-1 ends in 1111...
in binary. In JavaScript this is:
function isPowOf2(v){
return v && !(v & (v - 1));
}
var test = [0, 1, 2, 4, 6, 8];
for(var i = 0; i < test.length; ++i){
console.log(test[i] + " - " + isPowOf2(test[i]));
}
Applying to 8 you can see what is happening mathematically.
v = 8 = b1000 = true
v - 1 = 8 - 1 = 7 = b0111
8 & 7 = b1000 & b0111 = 0
!(8 & 7) = !(0) = true
v && !(8 & 7) = true
Q.E.D
Divide the number by two, until the rest of the division is less than or equal to 1 (use a loop for this)