05 Beginner The Hundred
The Shift That Wrapped Around
a trillion slots, give or take a trillion
#include <iostream>
// how many slots fit in a bits-wide address space?
long long slots(int bits) { return 1 << bits; }
int main() {
std::cout << "16-bit space: " << slots(16) << "\n";
std::cout << "40-bit space: " << slots(40) << "\n";
long long tebi = 1 << 40; // the same thing, spelled out
std::cout << "spelled out: " << tebi << "\n";
}
Run it. Do the two 40-bit answers agree — and is either of them 2^40?
Answer
Neither, and no. Typical output (GCC 11.5 on x86-64, no -O flag):
Why¶
A shift is evaluated in the type of its left operand, and 1 is an int — 32 bits
wide, so 16 is the only count here that fits. Shifting an int by 40 is undefined
behavior, and the widening to long long happens afterwards, on the wreckage. At -O0
the x86 shl instruction masks the shift count to its low 5 bits, so slots(40) really
executes 1 << 8 and returns 256; the spelled-out literal never reaches the CPU at all,
because GCC folds it at compile time — to 0. Rebuild at -O1 or higher and slots(40)
gets folded too, printing 0 as well: undefined behavior doesn't pick one wrong answer, it
picks whichever one is cheapest that day.
GCC flags the constant case by default, with no -Wall or -Wextra needed:
warning: left shift count >= width of type [-Wshift-count-overflow]. It can say nothing
about slots(40), where the count only exists at runtime — but -fsanitize=undefined
can: runtime error: shift exponent 40 is too large for 32-bit type 'int'.
The fix¶
Widen the left operand, before the shift rather than after:
long long slots(int bits) { return 1LL << bits; }
long long tebi = 1LL << 40; // 1099511627776, at every -O level
1ULL works the same way, and static_cast<uint64_t>(1) << bits says it out loud when
the width matters more than the spelling.
Takeaway: a shift is done in the type of its left operand — widen that side first,
because assigning to a long long is far too late.
Try it: g++ -std=c++17 main.cpp -o demo && ./demo