Math & Bit Manipulation, Power of X

Power of Two

妖孽的 trick。。

public class Solution {
    public boolean isPowerOfTwo(int n) {
        return (n > 0) && (((n - 1) & n) == 0);
    }
}

Power of Three

因为 3 不是 2 的整数倍，用二进制的各种 bit manipulation 是没前途的。。

不用循环解的话，要么 log ，要么 mod.

log 的解法是利用了 log 公式，如果不用 log10 的话会因为精度问题出错。（其实这个解法不管怎么说都需要考虑下 numerial analysis 提到过的精度问题。。）

 public static boolean isPowerOfThree(int n) {
    if (n <= 0)
        return false;
    double r = Math.log10(n) / Math.log10(3);
    if (r % 1 == 0)
        return true;
    else
        return false;
}

妖孽解法是。。1162261467 = 3^19，是整数中最大的 power of 3，所以如果 n 是 power of 3 的话一定可以整除这个数。

这么干和作弊差不多=。= 对喜欢问这种问题的公司致以深深的鄙视。

public class Solution {
    public boolean isPowerOfThree(int n) {
        return (n > 0) && (1162261467 % n == 0);
    }
}

Power of Four

一个数如果是 power of four，首先是 power of two.

除此之外，只会有一个 '1' 在固定可能的位置上，所以可以直接写个 mask

01010101010101010101010101010101 = 0x55555555

public class Solution {
    public boolean isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) > 0);
    }
}