美文网首页
IOS 算法(基础篇) ----- 4 的幂

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

作者: ShawnAlex | 来源:发表于2021-05-31 11:28 被阅读0次

    给定一个整数,写一个函数来判断它是否是 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 算法合集地址

    相关文章

      网友评论

          本文标题:IOS 算法(基础篇) ----- 4 的幂

          本文链接:https://www.haomeiwen.com/subject/cvavsltx.html