これはインタビューの質問です：
Javaクラスを1年ほど受講していないため、ブール値については非常に大雑把です。助けやアイデアがあれば大歓迎です。
4 つの要件をすべて満たす最善の方法nは、奇数または 1 になるまで半分にすることです。
def ispow(n):
while True:
if n == 1:
return True
if n % 2 == 1:
return False
n = n / 2
出力：
1 True
2 True
3 False
4 True
5 False
6 False
7 False
8 True
9 False
10 False
ティムの答えは、明らかにインタビュアーが求めているものです。
ただし、ルールを破ることで、より良い結果を得ることができます。
d. 一般に、非パワーはパワーよりも速く識別される必要があります。
BoppreH が指摘しているように、除算がないため、下向きではなく上向きにカウントする答えは (少なくともほとんどの言語とプラットフォームで) はるかに高速になります。彼の実装は、最悪の場合でも Tim の実装よりもほぼ 1 桁高速です。
もちろん、BoppreH の平均的なケースと最良のケースは基本的に最悪のケースと同じですが、Tim の場合は最良のケースがはるかに優れています。しかし、多くの場合、最悪のケースは非常に重要であるため、検討する価値のあるトレードオフであることは確かです。
または：
を。+ - * / % のみで、数学ライブラリやビット演算はありません
ティムのソリューションの遅い部分は除算演算子ですが、実際には必要ありません。、およびn % 2 == 1と置き換えることができます。これらは同等であることが保証されており、突然、最悪の場合は 1 桁速くなり、BoppreH よりも速くなります。n & 1n = n / 2n = n >> 1
これは、たとえば C ではコンパイラに期待されるようなことですが (もう一度、C で2**100000数学ライブラリを使用せずに処理してみてください…)、Python では (少なくとも CPython — おそらく PyPy を試してみる価値があります。 Jython や IronPython など)、手動で行う必要があります。そして、あなたは許可されるべきです。
そして、これが、この種のインタビューの質問が、さらなる議論の出発点である場合を除いて、愚かで無意味である理由です. 彼らが明らかに探している答えは、多くの場合、実際のコードで使用したい答えではありません。
より短く、反復ごとに乗算のみを実行します。
def is_power(x):
current_power = 1
while current_power < x:
current_power *= 2
return current_power == x
x = 2 ^ 100.000 のベンチマーク
number = str(2 ** 100000)
cProfile.run('is_power(' + number + ')')
cProfile.run('ispow(' + number + ')')
cProfile.run('is_pow_2(' + number + ')')
is_power (これ): 1.264 秒
ispow (ティムの答え): 11.455 秒
もう一つはまだ終わっていません…
他のすべてが失敗した場合は、強制を使用します。
def is_pow_2(x):
i=0
while 2**i <= x:
if x == 2**i:
return True
i += 1
return False
どうですか
import re
n = 2**5
print bool(re.match("^10*$",bin(n)[2:]))