LeetCode题练习与总结：4的幂--342

一、题目描述

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

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

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

提示：

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

二、解题思路

要判断一个整数是否是 4 的幂次方，我们可以利用以下性质：

1. 4 的幂次方一定是正数。
2. 4 的幂次方的二进制表示中，只有一个 1，且这个 1 出现在奇数位置上（从右边开始计数，第 1、3、5、… 位）。

基于以上性质，我们可以采用以下步骤进行判断：

1. 首先判断 n 是否大于 0，如果不大于 0，直接返回 false。
2. 然后判断 n 的二进制表示中是否只有一个 1。这可以通过 n & (n - 1) 来判断，如果结果为 0，说明 n 只有一个 1。
3. 最后判断这个 1 是否出现在奇数位置上。可以通过与一个特殊的数进行按位与操作来判断，这个特殊的数是一个只在奇数位置上为 1 的数，例如 0x55555555（十六进制）。

三、具体代码

class Solution {public boolean isPowerOfFour(int n) {// 0x55555555 是一个特殊的数，它的二进制表示为：01010101010101010101010101010101// 只在奇数位置上有 1，可以用来判断 4 的幂次方的 1 是否在奇数位置上return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;}
}

这段代码首先判断 n 是否大于 0，然后通过 n & (n - 1) 判断 n 是否只有一个 1，最后通过 n & 0x55555555 判断这个 1 是否在奇数位置上。如果这三个条件都满足，则 n 是 4 的幂次方。

四、时间复杂度和空间复杂度

1. 时间复杂度

在这个函数中，我们执行了以下操作：

• n > 0：这是一个常数时间的比较操作，时间复杂度为 O(1)。
• (n & (n - 1)) == 0：这是一个位操作，它会持续执行直到 n 变为 0。在最坏的情况下，n 是 2 的幂次方但不是 4 的幂次方，那么这个操作会执行 log2(n) 次（因为每次操作都会移除 n 的最低位的 1），所以这个操作的时间复杂度是 O(log n)。
• (n & 0x55555555) != 0：这是一个按位与操作，它也是常数时间操作，时间复杂度为 O(1)。

由于这些操作是顺序执行的，所以整个函数的时间复杂度取决于最耗时的操作，即 O(log n)。

2. 空间复杂度

在这个函数中：

• 我们没有使用任何额外的数据结构（如数组、集合、栈等）。
• 我们只使用了几个整型变量 n，(n - 1) 和 0x55555555，这些变量占用的空间是常数。

因此，空间复杂度为 O(1)，表示算法的额外空间需求不随输入规模增长而增长。

五、总结知识点

• 位操作符（Bitwise Operators）:

  • &（按位与操作符）：用于比较两个整数的二进制表示，只有在两个比较位都为 1 时，结果位才为 1。
  • -（减法操作符）：用于计算两个数的差，这里用于 (n - 1)。

• 逻辑操作符（Logical Operators）:

  • >（大于操作符）：用于比较两个数的大小。
  • ==（等于操作符）：用于比较两个数的值是否相等。
  • !=（不等于操作符）：用于比较两个数的值是否不相等。
  • &&（逻辑与操作符）：用于连接两个布尔表达式，只有两个表达式都为 true 时，结果才为 true。

• 特殊数值:

  • 0x55555555：这是一个十六进制常量，其二进制表示为 01010101010101010101010101010101，这个数值用于检测一个数的二进制表示中 1 的位置是否只在奇数索引上。

• 整数与二进制表示:

  • 整数在计算机中是以二进制形式存储的，代码中的位操作是基于整数的二进制表示进行的。

• 递归下降:

  • (n & (n - 1)) == 0 这个操作可以看作是一种递归下降的过程，每次操作都会将 n 的最低位的 1 置为 0，直到 n 变为 0。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。