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}\) |