How to determine if a number is a power of 2?

14

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?

    
asked by anonymous 01.06.2016 / 02:51

4 answers

9

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!

    
01.06.2016 / 04:27
12

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.

    
01.06.2016 / 03:09
12

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

    
01.06.2016 / 10:12
4

Divide the number by two, until the rest of the division is less than or equal to 1 (use a loop for this)

  • If the rest of the division equals 1, the number is a power of 2
  • If the rest of the division is less than 1 the number is not power of 2
01.06.2016 / 03:11