[LeetCode] 342. Power of Four

轉自LeetCode

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?

<Solution>
判斷 num 是不是 4 的次方數

這類型的題目，有個萬用解，就是換底公式，然後判斷是不是整數

和 Power of Three 一樣

code 如下

	class Solution {
	public:
	bool isPowerOfFour(int num) {
	return num > 0 && !(log10(num) / log10(4) - static_cast<int>(log10(num) / log10(4)));
	}
	};

view raw isIntPowerOfFour_1.cpp hosted with ❤ by GitHub

那和找 2 的次方數一樣，4 的次方數，其 binary format 也只會有一個為 1 的 bit

但 8 是 2 的次方數，不是 4 的次方數，要區別這點，還需要一個特性

也就是 4 的次方數，其值為 1 的 bit 只會出現在奇數位 (從 1 開始算)

所以可以用 num & 0x55555555 來判斷 1 的位置是不是在奇數位

因為題目有要求可不可以不要用 loop，所以使用 2 的次方數和4 的次方數都有的一個特性

num & (num - 1) = 0

code 如下(參考資料)

	class Solution {
	public:
	bool isPowerOfFour(int num) {
	return num > 0 && (!(num & (num-1)) && num & 0x55555555);
	}
	};

view raw isIntPowerOfFour_2.cpp hosted with ❤ by GitHub

或者使用下列特性

4 的次方數減1，會是 3 的倍數

當然，這個解法需要比較多數學運算，所以速度會比較慢

code 如下(參考資料)

	class Solution {
	public:
	bool isPowerOfFour(int num) {
	return num > 0 && (!(num & (num-1)) && (num-1) % 3 == 0);
	}
	};

view raw isIntPowerOfFour_3.cpp hosted with ❤ by GitHub