342. 4的幂

心已赠人 2023-02-11 07:14 91阅读 0赞

# 题目来源 #

[LEETCODE][]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 递归 ##

class Solution {
        
        public boolean isPowerOfFour(int num) {
        
          if (num == 1 || num == 4){
        
                return true;
            }
    
            if (num < 4){
        
                return false;
            }
    
            if (num % 4 != 0){
        
                return false;
            }
    
            return isPowerOfFour(num / 4);
        }
    }

![在这里插入图片描述][20200522095958739.png]

## 循环\[易错\] ##

class Solution {
        
        public boolean isPowerOfFour(int num) {
        
           if(num == 0)
                return false;
                
            while(num%4 == 0){
        
                num = num/4;
            }
    
            return num==1;
        }
    }

![在这里插入图片描述][20200522100748305.png]

## 查表 ##

class Solution {
        
        public boolean isPowerOfFour(int num) {
        
            return num == 1 || num == 4 || num ==16 || num == 64 || num == 256 || num == 1024 || num == 4096 || num == 16384 || num == 65536 || num == 262144 || num == 1048576 || num == 4194304 || num == 16777216 || num == 67108864 || num == 268435456 || num == 1073741824;
        }
    }

## 位运算 ##

*  4的幂一定是2的。
 *  4的幂和2的幂一样，只会出现一位1。但是，4的1总是出现在奇数位。

算法：

*  先判断是不是2的幂：num > 0 && n&(n-1) == 0
 *  4的幂和2的幂一样，只会出现一位1。但是，4的1总是出现在奇数位。
 *  奇数位的1 & （0b101010…10） = 奇数位的1 。 偶数位的1 &(0b101010…10) = 0
 *  (0b101010…10) 用十六进制表示为 ：0xaaaaaaaa

class Solution {
        
      public boolean isPowerOfFour(int num) {
        
        return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0xaaaaaaaa) == 0);
      }
    }

## 位运算 + 数学运算 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

class Solution {
        
      public boolean isPowerOfFour(int num) {
        
        return (num > 0) && ((num & (num - 1)) == 0) && (num % 3 == 1);
      }
    }

[LEETCODE]: https://leetcode-cn.com/problems/power-of-four/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200522095109374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200522095958739.png]: https://img-blog.csdnimg.cn/20200522095958739.png
[20200522100748305.png]: https://img-blog.csdnimg.cn/20200522100748305.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200522102609383.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70