Introduction

If the real task is computing 2^n mod d for 32-bit or 64-bit integers, the right answer is modular exponentiation. The naive approach of computing 2^n first and then taking the remainder fails quickly because the intermediate value overflows long before n becomes interesting.

Use Modular Exponentiation, Not Plain Shifts

For very small exponents, 1ULL << n may seem tempting. That only works while n stays below the machine word size and while the intermediate shift is still meaningful for your type. As soon as n is larger, or the modulus is not a power of two, that shortcut stops being a general solution.

The standard approach is exponentiation by squaring. Instead of multiplying by 2 exactly n times, you square the current base, reduce modulo d at each step, and only multiply into the result when the current exponent bit is set.

That gives O(log n) multiplications instead of O(n).

Core C++ Implementation

For 32-bit values, ordinary 64-bit intermediate multiplication is enough. For full 64-bit inputs, it is safest to use unsigned __int128 where available so the multiply-before-mod step does not overflow.

1#include <cstdint>
2#include <iostream>
3
4std::uint64_t pow2_mod(std::uint64_t n, std::uint64_t d) {
5    if (d == 0) {
6        throw std::invalid_argument("modulus must be non-zero");
7    }
8
9    std::uint64_t result = 1 % d;
10    std::uint64_t base = 2 % d;
11
12    while (n > 0) {
13        if (n & 1) {
14            result = static_cast<std::uint64_t>(
15                (static_cast<unsigned __int128>(result) * base) % d
16            );
17        }
18
19        base = static_cast<std::uint64_t>(
20            (static_cast<unsigned __int128>(base) * base) % d
21        );
22        n >>= 1;
23    }
24
25    return result;
26}
27
28int main() {
29    std::cout << pow2_mod(50, 1000000007) << "
30";
31}

This is fast, branch-light, and safe for ordinary competitive-programming and systems-level use on compilers that support unsigned __int128.

Why Reducing at Every Step Matters

The mathematical rule behind this algorithm is simple:

(a * b) mod d = ((a mod d) * (b mod d)) mod d

Because of that rule, you never need the full value of 2^n. You only need the running remainder. That is what keeps the numbers bounded and the computation practical.

For example, when d is one billion plus seven, 2^1000 is astronomically large, but the remainder can still be updated with ordinary fixed-width arithmetic if you reduce after each multiplication.

Special Cases Worth Handling

A few edge cases matter in real code:

• If d == 1, the answer is always 0.
• If n == 0, the answer is 1 mod d.
• If d == 0, the operation is invalid because modulo zero is undefined.

If performance is truly critical and the base is always 2, you can micro-optimize around that fact, but the asymptotic win already comes from exponentiation by squaring. Most hand-written bit tricks do not beat the clarity-to-speed ratio of the standard algorithm.

When a Shortcut Is Actually Valid

There is one family of shortcuts worth mentioning. If d is a power of two, then modulo becomes a bit mask, and the answer has strong structure. For example, x mod 8 is just x & 7. But you still cannot materialize 2^n directly for large n; the shortcut helps only after you reason about the modulus itself.

In other words, special moduli can simplify the final reduction, but they do not replace the general modular-power algorithm.

Common Pitfalls

• Computing 2^n first and overflowing before the modulo is applied.
• Using left shift as a universal replacement for modular exponentiation.
• Forgetting that 64-bit multiplication can overflow even when the final remainder fits in 64 bits.
• Ignoring the d == 0 case.
• Optimizing for tiny exponents and ending up with code that breaks on realistic inputs.

Summary

• The standard solution for 2^n mod d is exponentiation by squaring.
• Its time complexity is O(log n), which is far better than repeated multiplication.
• For 64-bit inputs, use a wider intermediate type such as unsigned __int128 when available.
• Reducing modulo d at each step prevents overflow from dominating the computation.
• Bit tricks help only in narrow special cases; modular exponentiation is the general answer.