How to calculate pow(2,n) when n exceeds 64 in c++?

An important detail here is that you're not being asked to compute 2n for gigantic n. Instead, you're being asked to compute 2n mod 109 + 7 for large n, and that's a different question.

For example, let's suppose you want to compute 270 mod 109 + 1. Notice that 270 doesn't fit into a 64-bit machine word. However, 270 = 230 · 235, and 235 does fit into a 64-bit machine word. Therefore, we could do this calculation to get 270 mod 109 + 7:

270 (mod 109 + 7)

= 235 · 235 (mod 109 + 7)

= (235 mod 109 + 7) · (235 mod 109 + 7) mod 109 + 7

= (34359738368 mod 109 + 7) · (34359738368 mod 109 + 7) mod 109 + 7

= (359738130 · 359738130) mod 109 + 7

= 129411522175896900 mod 109 + 7

= 270016253

More generally, by using repeated squaring, you can compute 2n mod 109 + 7 for any value of n in a way that nicely fits into a 64-bit integer.

Hope this helps!


The common approach in serious numerical work is to rewrite the formula's. You store log(x) instead of x, and later when you do need x it will typically be in a context where you didn't need all those digits anyway.