Why does an arithmetic right shift of a negative pixel delta not match integer division by two?
answer
- what fills the vacated high bits?
- rounding direction, not just magnitude
- try a negative odd value by hand
- floor versus truncate toward zero
- -7 shifted right by one
basics
~20 sAn arithmetic right shift rounds toward negative infinity; truncating integer division rounds toward zero. They agree on non-negative values and when the division is exact, but for -7 the shift gives -4 and the division gives -3.
solid answer
~50 sAn arithmetic right shift fills the vacated high bits with copies of the sign bit, so a negative value stays negative and the operation is exactly a floor-divide by a power of two. Truncating integer division, which is what most mainstream languages mean by `/` on integers, rounds toward zero instead. The two therefore disagree on exactly one class of input: negative values with a non-zero remainder. `-7 >> 1` is -4 while `-7 / 2` is -3. In a codec that halves signed pixel deltas, that difference is not a rounding curiosity — every negative odd delta is biased one step down, and across a frame those biases accumulate into visible drift. The contrast is a *logical* right shift, which zero-fills instead: applied to a negative value it turns the sign bit into an ordinary high bit and yields a large positive number.
go deeper
Remember that a right shift on a signed value keeps the sign by copying the top bit, and that it rounds downward rather than toward zero. Be able to state that -7 shifted right by one is -4.
Explain the mechanics: which bits fill the vacated high end, why sign propagation makes the shift a floor-divide by a power of two, and exactly which inputs make it disagree with truncating division.
Show how you would catch this in review and in tests: negative and odd values in the fixture set, an explicit statement of the rounding rule the format requires, and scepticism about swapping a division for a shift as an optimisation.
Own the format-level decision: rounding rules are part of a codec's contract, so pin them in the specification and in conformance tests rather than letting them be an accident of which operator someone reached for.
### Two different right shifts A right shift moves every bit down by k positions. The only question is what gets fed into the high end that the bits vacated. - **Logical (zero-fill) right shift** feeds in zeros. It is the correct shift for a value you regard as an unsigned bit pattern. - **Arithmetic (sign-propagating) right shift** feeds in copies of the top bit. Positive values get zeros — indistinguishable from a logical shift — while negative values get ones, so the result stays negative. For non-negative values the two are identical. The whole discussion is about negatives. ### Shift is floor division, `/` is truncating division An arithmetic right shift by k computes floor(x / 2^k): the exact quotient rounded *down*, toward negative infinity. Truncating integer division computes the exact quotient with the fractional part discarded, which rounds *toward zero*. For non-negative inputs, down and toward-zero are the same direction, so the two agree. For a negative input with a non-zero remainder they differ by exactly one: | x | exact x/2 | `x >> 1` (floor) | `x / 2` (truncate) | |---|---|---|---| | 7 | 3.5 | 3 | 3 | | -8 | -4.0 | -4 | -4 | | -7 | -3.5 | **-4** | **-3** | | -1 | -0.5 | **-1** | **0** | The `-1` row is the one that surprises people: shifting -1 right never reaches zero. Every position is already a 1 bit and the sign fill keeps supplying more, so -1 is a fixed point of arithmetic right shift. A loop written as "shift until the value becomes zero" runs forever on a negative input. ### Why it matters in a delta codec A delta-compression stage stores each sample as its difference from the previous one, and a lossy variant may halve those deltas before quantising. Replace the division with a shift "because shifts are faster" and you have quietly changed the rounding rule for half your data. Positive deltas behave as before; negative odd deltas each lose an extra unit. In a signal reconstructed by accumulating deltas, that is a systematic negative bias, and biases accumulate where symmetric rounding errors cancel — a long ramp drifts, and the drift is proportional to the number of samples, not to the amplitude of the noise. If you want floor semantics, the shift is not merely acceptable, it is the *clearer* way to say so. The defect is silently swapping one rounding rule for the other while the code claims to be an optimisation. ### Getting the rounding you actually want - **Want floor?** Use the arithmetic shift and say so in a comment; it is exact and branch-free. - **Want truncation toward zero?** Divide. Compilers already turn a power-of-two division into a shift plus a small correction for the negative case, so writing the shift by hand buys nothing but a bug — the correction step is precisely what you deleted. - **Want round-to-nearest?** Add half the divisor before shifting: `(d + (1 << (k-1))) >> k` rounds halves upward. Choose the tie-breaking rule deliberately, because for a codec the tie rule is part of the format. ### Where ecosystems disagree This is one of the places mainstream runtimes genuinely made different calls on the same concept. Java and JavaScript expose two distinct operators — one sign-propagating, one zero-filling — so the choice is at the call site. C, Go and Rust have a single right-shift operator whose behaviour follows the *signedness of the operand type*, so the choice is made by the declaration, sometimes far away from the shift. Older C and C++ standards left right-shifting a negative value implementation-defined; C++20 finally mandated the sign-propagating behaviour that every mainstream implementation already had. The portable habit that falls out: when you mean a bit pattern, hold it in an unsigned type; when you mean a number, mean floor or mean truncation and write the one you mean. ### The misconception to kill "Right shift is divide by two" is true for non-negative values and false in general. Its cousin, "left shift is multiply by two", has the same shape of exception at the other end: it holds only while the bits shifted off the top were not carrying meaning. Both shortcuts are fine as intuition and dangerous as a refactoring rule.
- What does a logical right shift do to a negative value?It zero-fills, so the sign bit stops being a sign and becomes an ordinary high bit. A small negative value turns into a very large positive one whose magnitude depends on the operand width. That is correct behaviour when the value is a bit pattern, such as a packed header word, and a serious bug when the value is a signed measurement.
- Why does shifting -1 right in a loop never terminate?Every bit of -1 is set, and the arithmetic shift keeps feeding fresh 1 bits into the top, so -1 shifts to -1 forever. Any loop with the condition "until the value is zero" hangs on negative input. Either shift a value held as an unsigned bit pattern, or bound the loop by the operand width instead of by reaching zero.
- If shifts and division differ, why do compilers turn a division by two into a shift?They emit a shift plus a correction for the negative case — typically adding a bias before shifting so the result rounds toward zero. You get the speed of the shift and the semantics of division. Hand-writing the bare shift removes the correction, which is exactly the bug: you kept the instruction and dropped the meaning.
Rounding down and rounding toward zero point the same way on the positive side of a number line and in opposite directions on the negative side, like two people told to 'go to the nearer wall' from opposite ends of a room.
saying these in an interview costs you the question
- Right shift is just integer division by two
- The vacated high bits are always filled with zeros
- Arithmetic and logical right shift differ only for unsigned values
- Shifting a negative value always yields a positive result
- A one-unit rounding difference cannot accumulate