ABC215 B問題 log2(N) を複数パターンで解く - 競技プログラミング悪戦苦闘日記

ABC215のB問題を複数パターンで解きます。

問題

正整数 $N$ が与えられるので、 $2^k \leq N$ となる最大の整数 $k$ を求めてください。
制約
$N$ は $1 \leq N \leq 10^{18}$ を満たす整数である

難しいポイント

条件式の両辺に $log_{2}$ をつけて式変形すると $k \leq log_{2}{N}$ となります。
やった簡単！ $log_{2}{N}$ を求めて、少数を切り捨てた値を出力したのですが、いくつかのパターンでWrong Answerとなります。
$N$ がとても大きい数だと誤った答えになってしまうようです。。。
私はこれで何回かハマりました。

1つ目の解き方の方針

$N$ を2進数で表して、桁数 - 1 が答えです。
例えば、 $N = 3$ だったら2進数で $11$ 、pythonのbinメソッドを使うと文字列で'0b11'となります。
なので、binメソッドで得られた文字列の長さから3を引いた数が答えになります。

1つ目の実装

N = int(input())
bin_str = bin(N)
print(len(bin_str) - 3)

2つ目の解き方の方針

基本の考え方は1つ目と同じです。
$N$ を2進数で表して、桁数 - 1 が答え。
10進数から2進数を求めるとき、ひたすら2で割ってあまりを並べることを思い出します。
$N = 5$ の時、 $5 \div 2 = 2 \cdots 1$ 、 $2 \div 2 = 1 \cdots 0$ 、 $1 \div 2 = 0 \cdots 1$ 、となって、 $101$ ということがわかります。
2で割る回数が桁数になっていることがわかります。
$N = 5$ の時、3回2で割ってますけど、求めたいのは桁数 - 1なので、1以下の時は割る必要はりません。
1以下になるまで2で割る回数をカウントして、そのカウントした回数が答えです。

2つ目の実装

N = int(input())
ans = 0
while N > 1:
    ans += 1
    N //= 2
print(ans)

簡単だったのですが、Wrong Answerを出してしまったのが悔しい。。。