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;
        }
  }