LeetCode 342.4的幂 -Java

问题描述

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

示例 1:

输入: 16

输出: true

示例2:

输入: 5

输出: false

解题思路

好多种方法可以求解该题.

分析:首先看4的二进制的特点,为1,100,10000…100000000, 1都在奇数位,0的个数为偶数个.

另外一种解释看大佬的是先确认是2的幂,然后对3求余,余1的话就是4的幂.

当然还可以用一直/4后取余是否为0.可惜这种方法超时了,暴力方法现在不可取.

代码演示

1.

public static boolean isPowerOfFour(int num) {
    if (num <= 0)
      return false;
    if (Integer.bitCount(num) == 1 ) { // 先看是否为2的幂
      if (Integer.toBinaryString(num).length() % 2 == 1) { // 位数是否为奇数
        return true;
      }
    }
    return false;
  }      

2.

public static boolean isPowerOfFour(int num) {
      if (num <= 0) {
        return false;
          } else if(num == 1) {
              return true;
          } else if(Integer.bitCount(num) == 1) {
        if (num%3==1) { // 对3求余是否为1
          return true;
        }
        return false;
      } else {
        return false;
      }
    }      

3.

public static boolean isPowerOfFour6(int num) {
        return num>0?(Integer.bitCount(num)==1 ?((num&0x55555555)!=0 ? true:false):false):false;
    }      

一行搞定,num&0x55555555的用意在于只保留奇数位的值. 因为4的幂的话,1一定在奇数位,所以相与后的结果是否与原数相等.

扩展开来就是:

if (num <= 0)

return false;

if (Integer.bitCount(num) == 1) { // 判断该数是否为2的幂

if ((num&0x55555555)!=0) { //若1在二进制奇数位，那么与0x55555555则为原数

return true;

}

}

return false;

4.

public static boolean isPowerOfFour(int num) {
    String str = Integer.toBinaryString(num);
    String s = str.replace("00", "");
    return s.equals("1");
  }      

刚开始的思路 (错误:超时)

public boolean isPowerOfFour(int num) {
    try {
        if(num == 1) { return true; }
        int temp = Integer.valueOf(Integer.toString(num, 4)); // 将该数转换为4进制数,因此temp的之值为1,100,10000...(可是这时temp为十进制数,不能认为是二进制.)
      while (temp%10 == 0) {
      temp /= 10; 
        }
            return temp == 1;
        } catch(Exception e) {
            return false;
        }
  }