Power of Number

判断一个数字是不是Power of 2/3/4

Power of Two

符合的数字是 000...00010, 000...00100, 000...01000

n & (n - 1) 相当于 000...00010 & 000...00001

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

不符合的数字比如3, 000...00011 & 000..00010， 结果一定不是0

Power of Three

计算 Math.log10(n) / Math.log10(3) 是不是可以得到一个整数。

n is a power of three if and only if i is an integer. In Java, we check if a number is an integer by taking the decimal part (using % 1) and checking if it is 0.

    public boolean isPowerOfThree(int n) {
        
        // return (Math.log10(n) / Math.log10(3)) % 1 == 0;
        
// The solution above is problematic because we start using doubles, which means we are subject to precision errors. 
// This means, we should never use == when comparing doubles. 
// That is because the result of Math.log10(n) / Math.log10(3) could be 5.0000001 or 4.9999999. 
// This effect can be observed by using the function Math.log() instead of Math.log10().

// In order to fix that, we need to compare the result against an epsilon.
        return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
    }

Power of Four

特殊方法1：

number n is a power of 4 if the following conditions are met.

1. There is only one bit set in the binary representation of n (or n is a power of 2)

2. The bits don’t AND(&) any part of the pattern 0xAAAAAAAA。 Why 0xAAAAAAAA ? This is because the bit representation is of powers of 2 that are not of 4. Like 2, 8, 32 so on.

For example: 16 (10000) is power of 4 because there is only one bit set， and 0x10 & 0xAAAAAAAA is zero.

public boolean isPowerOfFour(int n) 
{
    if (n <= 0) return false;
    return (n & (n - 1)) == 0) && (n & 0xAAAAAAAA) == 0;
}

特殊方法2:

0x55555555 is a hexametrical number，it is 1010101010101010101010101010101 in binary with a length of 32, and the 1 locates in the odd location.

public boolean isPowerOfFour(int num) {
    if (num <= 0) return false;
    
    // 常规方法: 适用于所有类似问题
    // int i = 0;
    // while (num != 0) {
    //     i += num % 4;
    //     num /= 4;
    // }
    // return i == 1;
    
    // 特殊方法：
    return (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
        
}