2の冪乗はとりあえず覚えとけ [GRE CS]

調子に乗って、GREサブジェクトCS分野問題5問目。

で、問題の形式としては、擬コードが示され、それについて云々……というタイプの問題なんだけど、よく見れば「コード解析」とか何とか、そんなことは関係なく、単なる数学（というか、算数）の問題。

要は、「x=1から始めて、2xで出た答えをまたxにぶち込んで再帰的に計算したとき、何回で1000を超える？」という問題。

これをトレースしてみると、

x=1: 21=2
x=2: 22=4
x=4: 24=16
x=16: 216=65536

ってなわけで、4回目で1000を超える（気をつけなくちゃいけないのは、コードをよく見ると、この4に1を足した5が答えになるように仕込んであること。ま、とはいえ、本質的なことではない）。

それで、CSにおいて「2の何乗か」ってのはよく問題になることなんで、次ぐらいは覚えておくべきだと思う。

21=2
22=4
24=16
28=256
216=65536
224=16777216
232=4294967296

他のパターンはこの表の数値をちょっと補正すれば、すぐ出るでしょ。たとえば、220は、16777216を16で割ればいいんだから、1048576だな、とか。