CONCEPT Cited by 1 source
Unsigned right shift (>>>)¶
Definition¶
Unsigned right shift (Java spelling: >>>) is the bit-shift
operation that treats its left operand as an unsigned bit
pattern, shifting in zeros from the high bits regardless of the sign
of the value interpreted as signed. Contrast with arithmetic
(signed) right shift (Java: >>; C/C++ >> for signed
operands), which performs sign extension — it shifts in copies of
the high bit, preserving sign.
| Operation | Java | C/C++ (signed) | C/C++ (unsigned) | Behaviour |
|---|---|---|---|---|
| Arithmetic right shift | x >> n |
x >> n (implementation-defined in C) |
— | Sign-extends |
| Logical right shift | x >>> n |
(unsigned)x >> n |
x >> n |
Shifts in zero |
Why it matters for the binary-search overflow bug¶
From Bloch, 2006, the canonical fix for the midpoint-of-two-indices overflow:
This works even when low + high has overflowed INT_MAX. The overflowed sum in two's-complement has its high (sign) bit set; interpreted as signed, it is a large negative number; interpreted as unsigned, it is the correct arithmetic sum treated modulo 2^32. Logical right-shifting the unsigned view by 1 performs the intended division by 2 on the true sum, producing the correct midpoint.
The key property: two's-complement wraparound + unsigned right shift recovers the correct answer for sum-and-halve arithmetic on the range [0, 2 · INT_MAX], which is exactly the range in which two non-negative int indices can sum.
C / C++ equivalent and a 2008 footnote¶
C and C++ do not have a dedicated unsigned-right-shift operator; the idiom is to cast to unsigned and shift:
Bloch's 2008 update (from Antoine Trux, Nokia Research) flagged that a signed-arithmetic C fix — relying on signed int overflow to wrap — is non-conformant per ISO/IEC 9899 §6.5 / C99: signed-integer overflow is explicitly undefined behaviour. The unsigned cast is the only portably correct shape. See concepts/integer-overflow for the broader substrate.
Performance¶
>>> typically compiles to a single machine shift instruction, the same cost as /2 on any modern CPU but with no division hazard. Bloch's framing: "probably faster, and arguably as clear" as the low + ((high - low) / 2) alternative in patterns/safe-midpoint-computation.
Other uses¶
- Building unsigned hashing / packing arithmetic on languages (Java, JavaScript pre-
BigInt) whose default integer type is signed. - Sign-agnostic bit manipulation when the high bit of a signed value carries a flag you want to shift out.
- Reading fields out of a packed signed representation without sign-extension contamination.
Seen in¶
- sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006 — Bloch's post explicitly benchmarks it as the preferred binary-search / mergesort midpoint fix: "
int mid = (low + high) >>> 1;— probably faster, and arguably as clear".