AtCoder ABC 215 B – log2(N) Python解説

2022年1月9日

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)