TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

01
 

2のn乗をざっくりと把握する

【作成日】 2021/08/22 22:56  【更新日】 

パッと言えるようになりたい2のn乗

競技プログラミングでは、\(2^n\)\(10^{9}\)など、○乗という表現がよくでます。

\(2^n\)とそれを\(10\)進法で表記した場合を一覧表にすると以下のようになります。

\(n\)\(2^n\)
\(0\)\(1\)
\(1\)\(2\)
\(2\)\(4\)
\(3\)\(8\)
\(4\)\(16\)
\(5\)\(32\)
\(6\)\(64\)
\(7\)\(128\)
\(8\)\(256\)
\(9\)\(512\)
\(10\)\(1024\)

数値(10のm乗)を2進数(2のn乗)に変換したときの桁数の見積もり

例えば、\(10^{12}\)\(2\)進数にしたときの桁数を知りたいとします。

上記の表から、\(2^{10}\)\(1024\)であるので、\(10^{3} < 2^{10}\)と言えます。

さらに、\(10^{12} = 10^{3\times4} \)なので、\(10^{3\times4} < 2^{10\times4}\)、すなわち、\(10^{12} < 2^{40}\)と言えます。

以上より、\(10^{12}\)\(2\)進数にしたときの桁数は\(40\)桁を超えることはないと見積もることができます。

大きい数をざっくりと表にする

上記の見積もり方法を知っていれば、表を暗記する必要はないが、念のために出会った値を表にしておきます。

\(2^n\) \(10^m\)(だいたい)
\(2^{20}\) \(10^{6}\)
\(2^{30}\) \(10^{9}\)
\(2^{40}\) \(10^{12}\)
\(2^{50}\) \(10^{15}\)
\(2^{60}\) \(10^{18}\)