Power of Four (E)
題目
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example 1:
Input: 16
Output: true
Example 2:
Input: 5
Output: false
Follow up: Could you solve it without loops/recursion?
題意
判斷一個數是不是4的冪次方，
思路
-
回圈判斷余數；
-
直接求對數再進行判斷；
-
找規律：
首先，\(4^{k+1}\)相當于將\(4^k\)的二進制向左移動兩位，初始從1開始，所以4的冪次方的二進制表示中一定只有一個1；
其次，因為每次向左移動兩位，這個1后面一定跟著偶數個0，1一定出現在從右向左第奇數個位置上，只要將num和\((0101)_2\)相與，只要結果不為0，那么這個1一定出現在奇數為上，
代碼實作
Java
回圈
class Solution {
public boolean isPowerOfFour(int num) {
while (num > 1) {
if (num % 4 != 0) {
return false;
}
num /= 4;
}
return num == 1;
}
}
對數
class Solution {
public boolean isPowerOfFour(int num) {
double n = Math.log(num) / Math.log(4);
return n == ((int) n) * 1.0;
}
}
找規律
class Solution {
public boolean isPowerOfFour(int num) {
return ((num & (num - 1)) == 0) && ((num & 0x55555555) != 0);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6730.html
標籤：其他
上一篇：【演算法】排序04——代碼簡約而不簡單的希爾排序（含代碼實作）
下一篇：《劍指offer》2:青蛙跳臺階