231 Power of Two – Easy
Problem:
Given an integer, write a function to determine if it is a power of two.
Thoughts:
The most straightforward is to use a recursion way. As shown in the first solution below. The running time of this solution will depends on how large the given Integer is, because for a number, 2^m, the running time will be (m).
The second solution is based on bit manipulation. Because if one integer is the power of two, it must starts with 1 and end with all trailing 0. So we can use a mask that starts with 10000…0 (31 0s), use & operation to find the first 1. Then we use ~ to get the opposite of the mask, e.g 00001000…00 will becomes 11110111…11, and use & with given integer, if given Integer is the power of 2, the result of & should be 0. This solution will run at most 32 iteration, so it’s O(1) time. This is better solution.
Solutions:
public class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
if (n == 1) {
return true;
}
if (n % 2 != 0) {
return false;
}
return isPowerOfTwo(n / 2);
}
}
public class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
if (n == 1) {
return true;
}
int mask = 1 << 31;
for (int i = 0; i < 31; i ++) {
if ((mask&n) != 0) {
break;
}
mask = mask >>> 1;
}
if ((n&(~mask)) == 0) {
return true;
}
else {
return false;
}
}
}
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
for (int i = 0; i < 32; i ++) {
if ((n&1) == 1) {
break;
}
n = n >>> 1;
}
n = n >>> 1;
return n == 0;
}
}