位运算 04

LeetCode 231

https://leetcode-cn.com/problems/power-of-two/

位运算

• 这里不讨论 O(logN) 的解法

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;
    }
}