首页 > 代码库 > 342. Power of Four

342. Power of Four

2024-09-04 19:35:31   218人阅读

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?


方法1：使用换底公式，跟Power of three同理

  1. public class Solution {
  2.     public bool IsPowerOfFour(int num) {
  3.         return (num > 0 && (int)(Math.Log10(num) / Math.Log10(4)) - Math.Log10(num) / Math.Log10(4) == 0);
  4.     }
  5. }

方法二：确定其是2的次方数了之后，发现只要是4的次方数，减1之后可以被3整除，所以可以写出代码如下：
  1. class Solution {
  2. public:
  3.     bool isPowerOfFour(int num) {
  4.         return num > 0 && !(num & (num - 1)) && (num - 1) % 3 == 0;
  5.     }
  6. };

下面这种方法是网上比较流行的一种解法，思路很巧妙，首先根据Power of Two中的解法二，我们知道num & (num - 1)可以用来判断一个数是否为2的次方数，更进一步说，就是二进制表示下，只有最高位是1，那么由于是2的次方数，不一定是4的次方数，比如8，所以我们还要其他的限定条件，我们仔细观察可以发现，4的次方数的最高位的1都是计数位，那么我们只需与上一个数(0x55555555) <==> 1010101010101010101010101010101，如果得到的数还是其本身，则可以肯定其为4的次方数：
  1. class Solution {
  2. public:
  3.     bool isPowerOfFour(int num) {
  4.         return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
  5.     }
  6. };




null


342. Power of Four


联系
我们