题目

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

示例 1：

输入：n = 27 输出：true

示例 2：

输入：n = 0 输出：false

示例 3：

输入：n = 9 输出：true

示例 4：

输入：n = 45 输出：false

提示：

-2^31 <= n <= 2^31 - 1

这类问题的解题思路

1.位运算法：

适用范围：仅当底数 n 是 2的幂 时（例如 2, 4, 8, 16...）才有效。

原因：这个技巧完全依赖于“2的幂”在二进制下的特殊表示形式（只有一个1）。对于底数3, 5, 6, 10等，它们的幂在二进制下没有这种简单规律，所以位运算技巧完全失效。

举例：4的幂

这个思路分为两步：

首先，判断 n 是否是 2 的幂。
然后，在所有 2 的幂中，筛选出那些同时也是 4 的幂的数。

第一步：判断 n 是否是 2 的幂

特性：一个正整数如果是 2 的幂，那么它的二进制表示中，有且仅有一个 1，其余位全为 0。
- 例如：4 的二进制是 100，8 是 1000，16 是 10000。
技巧：利用 n & (n - 1)。
- 如果 n 是 2 的幂（例如 10000），那么 n - 1 就是它后面所有位都为 1 的数（例如 01111）。
- 将这两者进行按位与（&）运算，结果必然是 0。
- 所以，n > 0 && (n & (n - 1)) == 0 是判断一个数是否为 2 的幂的经典方法。

第二步：从 2 的幂中筛选出 4 的幂

现在我们已经确定 n 的二进制里只有一个 1 了，我们还需要加一个条件。

特性：观察 4 的幂的二进制。
- 4^0 = 1 -> 1
- 4^1 = 4 -> 100
- 4^2 = 16 -> 10000
- 4^3 = 64 -> 1000000
规律：你会发现，4 的幂的二进制表示中，那个唯一的 1 总是出现在奇数位上（从右往左数，第1位，第3位，第5位...，如果把最右边记为第0位，那就是出现在偶数位上）。
如何利用这个规律？
- 方法A（数学模运算）：
  - 4^x - 1 必然能被 3 整除。
  - 证明：4^x - 1 = (2^x - 1)(2^x + 1)。2^x-1, 2^x, 2^x+1 是三个连续的整数，其中必有一个是3的倍数。而2^x不可能是3的倍数，所以 2^x-1 或 2^x+1 一定是3的倍数。因此，4^x-1 总是3的倍数。
  - 所以，我们只需要在判断 n 是 2 的幂的基础上，再加一个条件 (n - 1) % 3 == 0。
- 方法B（位掩码）：
  - 我们可以创建一个“掩码”（mask），这个掩码的二进制位是 01010101...。在32位整数中，它就是十六进制的 0x55555555。
  - 这个掩码在所有偶数位上是 1，奇数位上是 0。
  - 如果 n 是 4 的幂，它的 1 在偶数位上。那么 n 和这个掩码进行按位与（&）运算，结果应该还等于 n 本身。
  - 所以，附加条件可以是 (n & 0x55555555) == n。

最终的位运算解法（推荐使用方法A，更简洁）:

一个数 n 是 4 的幂，需要同时满足三个条件：

n 是正数 (n > 0)。
n 的二进制表示中只有一个 1 ((n & (n - 1)) == 0)。
n - 1 可以被 3 整除 ((n - 1) % 3 == 0)。

2.整数范围限制法：

适用范围：仅当底数 n 是质数时（例如 2, 3, 5, 7, 11...）才有效。

原因：这个技巧依赖于质数的性质。如果 n 是一个质数，那么 n 的 k 次方的所有约数必然是 n 的 j 次方 (其中 j <= k)。

反例：如果底数 n 是一个合数但不是2的幂（例如 n=6），这个方法就会出错。int 范围内6的最大幂是 612。但是 612 的约数有很多，比如 2, 3, 4, 9, 12... 这些都不是6的幂。如果你用 (6^12 % 12 == 0) 来判断12是否是6的幂，会得到错误的结果 true。

举例：3的幂

题目限制：我们处理的 n 通常是在一个给定的整数类型范围内，比如32位有符号整数 int。它的最大值是 2^31 - 1 (大约 2 * 10^9)。
寻找最大值：在这个范围内，最大的3的幂次方是多少？我们可以通过计算 log_3(Integer.MAX_VALUE) 来找到。
- log_3(2147483647) ≈ 19.59
- 这意味着在 int 范围内，最大的3的幂是 3^19。
- 319=1162261467。
利用质数特性：数字3是一个质数。因此，如果一个数是3的幂，那么它的所有因子（除了1）都必须是3。换句话说，一个数 n 是 3^x 的形式，当且仅当它是 3^19 (这个范围内的最大3的幂) 的约数。
最终判断：
- 首先，n 必须是正数。
- 然后，我们只需要检查 1162261467 是否能被 n 整除。

具体代码

4的幂

数学技巧

class Solution {
public:
    /**
     * @brief 判断一个整数是否是4的幂次方
     * @param n 输入的整数
     * @return 如果是4的幂则返回true，否则返回false
     */
    bool isPowerOfFour(int n) {
        // 1. n > 0: 4的幂次方必须是正数。
        // 2. (n & (n - 1)) == 0: 确保n是2的幂次方（二进制表示中只有一个1）。
        // 3. (n - 1) % 3 == 0: 从2的幂中筛选出4的幂。
        //    因为 4^x - 1 = (2^x - 1)(2^x + 1)，这个数总能被3整除。
        return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0;
    }
};

位掩码

class Solution {
public:
    bool isPowerOfFour(int n) {
        // 条件1和2同上：必须是正数且是2的幂。
        // 条件3: (n & 0x55555555) != 0 确保这个唯一的'1'出现在偶数位上。
        // 0x55555555 是一个32位整数，其二进制为 01010101010101010101010101010101
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
    }
};

3的幂

class Solution {
public:
    bool isPowerOfThree(int n) {
        // 1162261467 是 int 范围内最大的3的幂 (3^19)
        // 如果 n 是3的幂，那么它必然是这个最大幂的约数。
        return n > 0 && 1162261467 % n == 0;
    }
};

326. 3 的幂

beautifulremi

题目