How will you check if a number if a power of two or not?
For example: 4, 8, 1024 etc are powers of two. But 6, 40, 95 etc are not
Method-1: Take log to the base 2
This is pure mathematical solution to the problem. If log2(n) is integer than n is a power of 2, else not.
Method-2: Keep dividing by 2
Keep dividing the number by two, i.e, do n = n/2 iteratively until n becomes 1. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.
/** Check if a number is a power of 2 or not. * IF n is power of 2, return 1, else return 0. */ int powerOfTwo(int n) { if(n==0) { return 0; } while(n != 1) { n = n/2; if(n%2 != 0 && n != 1){ return 0; } } return 1; }
Method-3: Use Bitwise operators
This uses two facts:
N = 4, 000100 N-1 = 3, 000011 N = 16, 010000 N-1 = 15, 001111
Hence, If a number is a power of 2 then
N & (N-1)
Will be zero.
The only exception to above rule is when N is Zero. It will give zero as a power of two, which actually is not. Hence, in the check, we can see this explicitly.
/** Check if a number is a power of 2 or not. * IF n is power of 2, return 1, else return 0. */ int powerOfTwo(int n) { return n && (!(n & (n-1))); }
No related posts found
11 Comments
The second method looks invalid, please check.
its valid for all numbers
if its not then just reply that number here
Thanks for the methods. Will method 2 work the number 12 that is not power of 2 ?
[…] Kaynak whatever whatever […]
[…] Kaynak Étiquetteswhatever […]
[…] La Source […]
Method-3: Use Bitwise operators.
Wrong Code.- The operator ! is undefined for the argument type(s) int
Inside the while loop of Method 2, “n = n/2;” should be placed after “if(n%2 != 0 && n != 1){ return 0; }”
method two should be (n > 1) not (n != 1)
—————————————————–
n = int(input())
state = “YES”
while n > 1:
n = n / 2
if n % 2 != 0 and n != 1:
state = “NO”
else:
state = “YES”
print(state)
A Very Good Method In programming languages is to anding two numbers like
N = int (input())
If N != (N&-N): print yes
Else no
Method 2 will only work if n is a double or a float, since it will be cast to an int after n=n/2.
Another option of course is initializing a new double that will take the value of n before the while loop, in case changing the input of the function is not an option.