Search in a matrix sorted on rows & columns
June 12, 2012Output of a C function
June 12, 2012Check if number is a power of 2
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
Solution:
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:
- If the number is a power of two, then only 1 bit will be set in its binary representation.
- If we subtract 1 from a number which is power of 2, then all the bits after the set-bit (there is only one set bit as per point-1) will become set and the set bit will be unset. i.e:
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)));
}
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.