位运算 04
https://leetcode-cn.com/problems/power-of-two/
位运算
class Solution {
public boolean isPowerOfTwo(int n) {
if (n == 0) return false;
while (n % 2 == 0) n /= 2;
return n == 1;
}
}
-
首先要清楚,2的幂二进制表达是高位
只有
一个1,后面全是0。同时也要保证是个正数。
以下的公式证明推到戳这里:
https://www.jianshu.com/p/fec960ffb7af
-
法一:
x & (-x)
可以获得 x 二进制的最后一位
1
组成的数,
x & (-x) == x
即可判断
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
long x = (long) n;
return (x & (-x)) == x;
}
}
-
法二:
x & (x - 1)
可以将最后的那个
1
去掉,
x & (x - 1) == 0
即可判断
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
long x = (long) n;
return (x & (x - 1)) == 0;
}
}