快速判断x的幂——x进制法

1.快速判断一个数是否为2的幂

思路：
如果一个数是2的幂，那么它的二进制数一定只含有一个1，反过来也成立
快速判断一个数是否为2的幂，只需要把它写成二进制，然后获取1出现的次数
如果1只出现一次，那么必然有 x & (x-1) == 0，必然x是2的幂
因此，通过表达式 x > 0 and x & (x-1) == 0 即可快速判断2的幂

2.快速判断一个数是否为4的幂

思路1：
如果一个数是4的幂，那么它一定是2的偶数次幂，也就是对应的二进制数从右往左数，只奇数位置上出现且仅出现一个1

以下为go语言版，num为32位有符号整数

func isPowerOfFour(num int) bool {
    // 2的偶数次幂
    // 把这个数转换为二进制，只在奇数位置上存在一个1，其他全是0
    var v int
    var one_cnt int = 0
    for i:= 1; i < 33; i ++ {
        v = num & 1
        if i % 2 == 0 {
            if v != 0 {
                return false
            }
        }else {
            if v == 1 {
                one_cnt ++
            }
        }
        num = num >> 1
    }
    return one_cnt == 1
}

思路2：
把nums变成一个4进制数，如果只出现一个1，其他都是0，则是4的幂

func isPowerOfFour(num int) bool {
    one_cnt := 0
    var m int
    for num != 0 {
        // m指求mod，得到4进制数的digit
        m = num % 4
        num = num / 4
        if m > 1 {
            return false
        }else if m == 1{
            one_cnt ++
        }
    }
    return one_cnt == 1
}

3.小结

把一个数num转换为x进制，就是求num的【x幂多项式】表达。如果这个x幂多项式只有一项，那么num必然是x的幂