AtCoder ABC 215 B – log2(N) Python解説
log2(N)
正整数 N が与えられるので、 2^k≤N となる最大の整数 k を求めてください。
AtCoder Beginner Contest「log2(N)」
基本的な解き方としては、kの値を1ずつ大きくしていき、2^k > Nになるまでループ回す方法があります。なので今回は、While文を使って2^k > Nになるまで、kの値を大きくしていきます。
n = int(input())
k = 0
while True:
if 2 ** k > n:
print(k - 1)
break
else:
k += 1
While Trueと書くとbreakされるまで処理がループします。if 2 ** k > nが成り立つとき、2^k <= N となる最大の整数kはひとつ前のkなので、k – 1を出力してbreakします。条件が成り立たなければk + 1で再度ループします。
bit演算を利用した解法もあります。先にまとめると、Nの2進数の桁数を使った解法です。
2^k 10進数 2進数
0 1 1
1 2 10
2 4 100
- 6 110 <---(例題)Nが6の場合
3 8 1000
4 16 10000
5 32 100000
上記のように、2^kのkの値が1増えると2進数では1桁ずつ増えていきます。この性質を利用して問題を解いてみます。Nが6だとしたら6の2進数は110なので、
2^k <=Nを満たすkの最大値はkが2のとき(100 <= 110 < 1000)です。
このように、Nと2^kが同じ桁数になるときが2^k <= Nを満たすkの最大値になります。
また、Nの桁数-1とすると、kの値を求めることができます。(Nが6のとき、6は2進数で3桁なので、2^kのkの値は3-1で2になります。)
Pythonではbit_length関数が用意されているので、こちらを使いましょう。
n = int(input())
print(n.bit_length() - 1)