Leetcode

LeetCode-4の累乗



Leetcode Power Four



説明：
整数（符号付き32ビット）が与えられた場合、それが4の累乗であるかどうかをチェックする関数を記述します。

例1：



Input: 16 Output: true

例2：

Input: 5 Output: false

ファローアップ： ループ/再帰なしでそれを解決できますか？



意図：32ビット整数が4の累乗であり、ループや再帰を必要としないかどうかを計算します

解決策：まず、次のように、32ビット未満の4の累乗と2の累乗の2進表現を最初に観察しましょう。

に 2 k 2 ^ k 4 k 4 ^ k
0 1 1
1 10 100
二 100 10,000
3 1000 1000000
4 10,000 100000000
5 100,000 10000000000
⋯ cdots ⋯ cdots ⋯ cdots

次の結論を導き出すことができます。



  • 整数が2の累乗として表現できる場合、その2進表現には1 1のみが含まれ、残りは0です。
  • 整数が4の累乗として表現できる場合、その2進表現には1つだけが含まれ、残りは0であり、1の位置は奇数であり、0の数は偶数です。

したがって、最初に、この整数の2進表現に1つしか含まれておらず、残りがすべて0であるかどうか（つまり、2の累乗として表現でき、の累乗を表すには2の累乗が必要かどうか）を判断できます。 4.状態）

num & (num - 1) == 0

十分条件を満たすためには、1の位置が奇数であるという要件（つまり、2の累乗を除いて奇数の累乗を持つもの）の要件の上に要件を追加する必要もあります。

num & 0x55555555 == 0 // 0x55555555(1010101 01010101 01010101 01010101)
Java
class Solution { public boolean isPowerOfFour(int num) { if (num == 0) return false return (num & (num - 1)) == 0 && (num & 0x55555555) != 0 ? true : false } }