0342. 4的幂 Power of Four

问题描述

这个问题与 0231. 2 的幂 Power of Two 很相似, 可以参考下它的解法.

方法1, 暴力法

直接找到所有 4^x 的值, 看它们是否与目标整数相等.

         1 = 0b00000000000000000000000000000001
         4 = 0b00000000000000000000000000000100
        16 = 0b00000000000000000000000000010000
        64 = 0b00000000000000000000000001000000
       256 = 0b00000000000000000000000100000000
      1024 = 0b00000000000000000000010000000000
      4096 = 0b00000000000000000001000000000000
     16384 = 0b00000000000000000100000000000000
     65536 = 0b00000000000000010000000000000000
    262144 = 0b00000000000001000000000000000000
   1048576 = 0b00000000000100000000000000000000
   4194304 = 0b00000000010000000000000000000000
  16777216 = 0b00000001000000000000000000000000
  67108864 = 0b00000100000000000000000000000000
 268435456 = 0b00010000000000000000000000000000
1073741824 = 0b01000000000000000000000000000000

然后, 代码也比较直接:

#![allow(unused)]
fn main() {
// Brute Force
pub fn is_power_of_four1(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    if n == 1 {
        return true;
    }

    let mut power = 1;
    while 0 < power && power < n {
        power <<= 2;
        if power == n {
            return true;
        }
    }
    false
}
}

方法2, 递归法

这个方法是根据题目要求实现的, 也是 余数与商(DivMod) 问题.

div-mode

如果整数 n 是4的次幂, 即 n == 4^x:

  • 那么 n / 4 == 4 ^ (x - 1) 等式也是成立的, 即 n / 4 也是4的次幕
  • 而且 n % 4 == 0

基于上面的等式, 可以很容易地写出递归的代码:

#![allow(unused)]
fn main() {
// 递归法
pub fn is_power_of_four2(n: i32) -> bool {
    if n == 1 {
        return true;
    }
    if n <= 0 || n % 4 != 0 {
        return false;
    }
    is_power_of_four2(n / 4)
}
}

方法3, 重写递归法为迭代的形式

这个就比较简单了, 但要注意边界条件.

#![allow(unused)]
fn main() {
// 把递归法改写为迭代的形式
pub fn is_power_of_four3(n: i32) -> bool {
    if n == 0 {
        return false;
    }
    if n == 1 {
        return true;
    }

    let mut n = n;
    while n % 4 == 0 {
        n /= 4;
    }
    n == 1
}
}

方法4, 利用 4^x 的特性

注意看方法1中展示出的 4^x 整数的二进制形式, 是不是很有特点?

  • 只有一个比特位的值为1
  • 低位比特位为0的个数是偶数个, 这个也好理解, 因为 4^x 就相当于 x << 2, 要左移2位, 自然在低字节位会留下偶数个的0

利用以上这两个条件就可以判断整数是否为4的次幂, 代码如下:

#![allow(unused)]
fn main() {
// 整数为 4^x 的特性
pub fn is_power_of_four4(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    n.count_ones() == 1 && n.trailing_zeros() % 2 == 0
}
}

相关问题