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

Question

So, I am new to programming in c++ and i came across this question where i need to calculate pow(2,n)/2 where n>64 ?

i tried using unsigned long long int but as the limit of the c++ is only 2^64. So is there any method to calculate this.

Edit:

 1 < n < 10^5

The result of the expression is used in further calculation

The question is asked on online platform.So, i cant use libraries like gmp to handle large numbers.

Question

You are given with an array A of size N. An element Ai is said to be charged if its value (Ai) is greater than or equal to Ki. Ki is the total number of subsets of array A that consist of element Ai.
Total charge value of the array is defined as summation of all charged elements present in the array mod (10^9)+7.
Your task is to output the total charge value of the given array.

Answer 1

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

For example, let's suppose you want to compute 2⁷⁰ mod 10⁹ + 1. Notice that 2⁷⁰ doesn't fit into a 64-bit machine word. However, 2⁷⁰ = 2³⁰ · 2³⁵, and 2³⁵ does fit into a 64-bit machine word. Therefore, we could do this calculation to get 2⁷⁰ mod 10⁹ + 7:

2⁷⁰ (mod 10⁹ + 7)

= 2³⁵ · 2³⁵ (mod 10⁹ + 7)

= (2³⁵ mod 10⁹ + 7) · (2³⁵ mod 10⁹ + 7) mod 10⁹ + 7

= (34359738368 mod 10⁹ + 7) · (34359738368 mod 10⁹ + 7) mod 10⁹ + 7

= (359738130 · 359738130) mod 10⁹ + 7

= 129411522175896900 mod 10⁹ + 7

= 270016253

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

Hope this helps!

Answer 2

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.