Power of Four-Leetcode

梦里梦外; 2022-07-30 13:53 147阅读 0赞

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:  
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

题目大意：判断一个数是不是4的幂。最好不要用递归和循环。

我擦，不用递归和循环，首先想到的就是从二进制层面去思考，之前遇到过一道题是判断一个数n是不是2的幂。直接判断n&(n-1)是不是等于0,简单粗暴。那么这道题和它很像。分析一下如果一个数是4的幂，那么它的二进制有什么特点？这里我发现只要是4的幂，那么它的二进制位只有一个1，其余都为0，并且1在奇数位。举个例子，16是4的2次幂。16的二进制是00010000（注意1在第5位），64的二进制是01000000（1在第7位）。所以我可以先判断一个数是不是2的幂，如果是，然后再判断1的位置是不是在奇数位，就可以了。如何判断是不是在奇数位？由于是32位的整数，所以1只可能出现在1,3,5,7.。。。。。31这些位置。因此我们乘以0x55555555即可。代码如下：

bool isPowerOfFour(int num) {
          if((num&(num-1))==0)
          {
              if(num&0x55555555)
              {
                  return true;
              }
          }
          return false;
        }

既然说到4的幂，那么这里顺便说一下2和3的幂问题。

如何判断一个数n是不是2的幂？之前我们说过直接n&(n-1)即可。代码如下：

bool isPowerOfTwo(int num)
    {
    	 if ((num&num - 1)==0)
    	 {
    		 return true;
    	 }
    	 return false;
    
    }

在这里,n&(n-1)还有一个作用，就是判断一个数的二进制中1的个数。代码如下：

int hammingWeight(uint32_t n) {
            int count=0;
            while(n)
            {
                count++;
                n=n&(n-1);
            }
            return count;
        }

如何判断一个数n是不是3的幂？如果一个数是3的幂,那么它的乘数因子也必然是3的幂，比如27等于9\*3,9和3是3的幂。所以这里我们只要在整数能表示的范围内，找到3的最大次幂m，然后判断m%n==0即可。代码如下：

bool isPowerOfThree(int num)
    {
    	 int max = pow(3,(int)(log(INT_MAX) / log(3)));
    	 return max % num == 0;
    
    }