判断数是否是4的幂次方。c++

判断一个数是否是4的幂次方，可以使用以下两种方法：

方法一：使用循环迭代

思路：不断将数除以4，如果最后得到1，则该数是4的幂次方；否则，该数不是4的幂次方。

代码如下：

int isPowerOfFour(int num) {
    while (num > 0 && num % 4 == 0) {
        num /= 4;
    }
    return num == 1;
}

方法二：使用数学公式

思路：4的幂次方可以表示为 $4^n$ 的形式，而 $4^n$ 可以表示为 $(3+1)^n$，根据二项式定理展开可得：

$$
4^n = (3+1)^n = \sum_{k=0}^{n} C_n^k3^k
$$

其中 $C_n^k$ 表示组合数，当 $k=0$ 或 $k=n$ 时，$C_n^k=1$，因此可以简化上式为：

$$
4^n = 1 + 3 + 3^2 + \cdots + 3^{n-1} + 3^n
$$

因此，如果一个数是4的幂次方，那么它的二进制表示中只有一个1，并且这个1在奇数位上（从右往左数）。因为 $4=100_2$，$16=10000_2$，$64=1000000_2$，可以发现，4的幂次方的二进制表示中，1总是在偶数位上，因此可以通过判断奇偶性来判断一个数是否是4的幂次方。

代码如下：

int isPowerOfFour(int num) {
    return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}

其中，`(num & (num - 1)) == 0` 用于判断是否只有一个1，`(num & 0x55555555) != 0` 用于判断1是否在奇数位上。