IOS 算法(基础篇) ----- 4 的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
其中： -2^31 <= n <= 2^31 - 1

例子：

输入：n = 16
输出：true

输入：n = 5
输出：false

输入：n = 1
输出：true

方法一： 遍历法

这种方法比较容易理解， 即依次除以4（用开方也行）判断是否满足余数为0时候是否为1 即 2^0 = 1(当然0要除外)

留意0以下直接false， 肯定不满足， 因为最小4^0 = 1

代码

    func isPowerOfFour(_ n: Int) -> Bool {

      if n <= 0 { return false }
    
      var temp = n
    
      while temp % 4 == 0 {
        temp /= 4
      }
  
      return temp == 1
    }

方法二： 进制法

建议先做下IOS 算法(基础篇) ----- 2 的幂

二进制按位与运算， 因为-2^31 <= n <= 2^31 - 1,其实我们考虑 0 < n < 2^31 - 1 即可，因为负数0肯定不是4的次方

首先如果是4次方， 则肯定是2次方， 所以我们先判断是否为2次方， 2次方有特性， 按位与 n & (n - 1)) == 0

例如：
n = 16 = 10000（二进制） ， n - 1 = 15 = 01111（二进制）， 按位与&一下（1&1 = 1， 1&0 = 0， 0&0 = 0）

10000
&
01111
= 0

如果是4次方那么奇数位为1且只有1个位置为1，
例如:
4^0 = 1 = 0000001
4^1 = 4 = 0000100
4^2 = 16 = 0010000
4^3 = 64 = 1000000
...

那么我们在规定范围内定义一个最大的二进制 10101010101010101010101010101010 按位与一下， 如果为0则满足需求
10101010101010101010101010101010（二进制） = 2863311530（十进制） = 0xaaaaaaaa（16进制）
还是拿16举例：

10101010101010101010101010101010
&
00000000000000000000000000010000
= 0

可能有些不明白为什么先判断2次方

拿5举例， 5 = 2^2 + 2^0 = 0101
00000000000000000000000000000101
&
10101010101010101010101010101010
= 0
但是5并不是4次方， 因为5并不满足只有1个位置为1

十进制
16进制

代码

    func isPowerOfFour(_ n: Int) -> Bool {
      // return n > 0 && (n & (n - 1)) == 0 && (n & 2863311530) == 0;
      return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }

方法三： 取余法

在方法二基础上改良下， 因为如果是4次幂则必有 n % 3 == 1;
先判断 n>0 且 n是2次方， 第三个判断条件用 n % 3 == 1判断

    func isPowerOfFour(_ n: Int) -> Bool {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址