Problem
Solution
Method1
All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2. We have discussed how to count number of bits set here.
Method 2
Note that the bit pattern of a power of two is of the form 10...0 and that of a number just one less is 011...1. Hence if we have & operator between the 2, we will get 0.We have discussed the solution here. Also, as 0 is not in power of 2, we have to explicitly check if n is greater than 0.
C code :
Method 3 - Complement and compare
C code
Method 4
C code
Method 5 - Shift right
Method 6 - Divide the number by 2 until it becomes 0
Method 7 -Take log of number and check if it is integer
A simple method for this is to simply take the log of the number on base 2 and if you get an integer then number is power of 2.
FOLLOW UP - Clearly Method 2,3 and 4 one-liners and are using bit hacks.
Please share if you have some method not covered above.
Check if integer is power of 2 or notFOLLOW UP - Preferable solution to get it in 1 line.
Solution
Method1
All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2. We have discussed how to count number of bits set here.
Method 2
Note that the bit pattern of a power of two is of the form 10...0 and that of a number just one less is 011...1. Hence if we have & operator between the 2, we will get 0.We have discussed the solution here. Also, as 0 is not in power of 2, we have to explicitly check if n is greater than 0.
C code :
bool isPowerOfTwo(int n) { return (n > 0) && ((n & (n - 1)) == 0); }
Method 3 - Complement and compare
C code
bool isPow2 = ((x & ~(x-1))==x)? x : 0;
Method 4
C code
bool isPowerOfTwo(int i){ return i>0 && ((i & -i) == i); }
Method 5 - Shift right
private static bool IsPowerOfTwo(ulong number) { while (number != 0) { if (number == 1) return true; if ((number & 1) == 1) // number is an odd number and not 1 - so it's not a power of two. return false; number = number >> 1; } return false; }
Method 6 - Divide the number by 2 until it becomes 0
bool isPowerOfTwo(int n) { if (n == 0) return 0; while (n != 1) { if (n%2 != 0) return 0; n = n/2; } return 1; }
Method 7 -Take log of number and check if it is integer
A simple method for this is to simply take the log of the number on base 2 and if you get an integer then number is power of 2.
FOLLOW UP - Clearly Method 2,3 and 4 one-liners and are using bit hacks.
Please share if you have some method not covered above.
0 comments:
Post a Comment