AtCoderログ：0091 - ABC 215 B

問題

問題文

正整数 $N$ が与えられるので、 $2^k \le N$ となる最大の整数 $k$ を求めてください。

制約

・$N$ は $1 \le N \le 10^{18}$ を満たす整数である

回答

回答1 (AC)

入力された $N$ に対し $2^1, 2,2,...$ を計算していき、はじめて $N < 2^i$ となる $i$ が見つかるまで繰り返すことにしました。コードは以下のようになりました。

abc215b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t n;
  cin >> n;

  int i = 0;
  int64_t p = 1;
  while ( p<=n ) {
    p *= 2;
    i++;
  }
  
  cout << i-1 << endl;
}

回答2 (WA)

設問の式の両辺の対数をとると $\log_2{2^k} \le \log_2{N}$ つまり $k \le \log_2{N}$ となるので、$\log_2$ の整数部分が求める $k$ の値となります。コードは以下のようになりますが、残念ながら WA となります。これは、$\log_2$ の計算精度が低いことが原因です。

abc215b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t n;
  cin >> n;
  
  cout << floor(log2(n)) << endl;
}

回答3 (AC)

回答2において、$\log_2$ への入力値を double にすると出力値も double となり、精度問題が解決できます。コードは以下のようになりました。

abc215b-3.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t n;
  cin >> n;
  
  cout << floor(log2((long double)n)) << endl;
}

調べたこと

AtCoder の解説 → 公式解説

3種類の回答が紹介され、最初の2つは回答1、回答3と同じ方針、3つ目は $N$ の2進展開を利用していました。

AtCoder の解説 → ユーザ解説

公式解説の3つ目の解法が、言語によってはライブラリにヨウイされているそうです。

リンク

前後の記事

• 前の記事 → AtCoderログ：0090 - ABC 215 A