Check Power of Two
Explain what the following code does: ((n & (n-1)) == 0)
Solution
n = abcde1000
n - 1 = abcde0111
can only have one 1 in the binary form -> check power of 2
注意判断 n > 0
注意因为对时间复杂度有要求,所以必须利用位操作来进行判断。注意一些边界情况,例如是负数或者是0,1 之类的,需要分别处理。
2 的幂次表示在二进制中只有最高位是 1 其余都是零,所以利用 n & n-1 == 0
来进行检测
Complexity
时间复杂度 O(1) 空间复杂度 O(1)
Code
public class Solution {
public boolean isPowerOfTwo(int n) {
return (n > 0) && (n & (n-1)) == 0;
}
}