6. Shifts: Moving Bits Left and Right

The concept

Lesson 5's four operations each computed a new value at every position from the input bit(s) already sitting at that same position — position 3 only ever talked to position 3, and nothing moved. Shifts break that rule on purpose: every bit relocates to a different position. That's still not the carrying Lessons 2 and 4 warned about, though — nothing is generated by combining two bits together. Each bit just slides over unchanged, one whole position at a time, and one bit falls off the end while a fresh 0 fills the gap left behind.

• Left shift: every bit moves toward a more significant position (one index higher). A new 0 enters at bit 0 (the right end). This multiplies the value by 2 (ignoring overflow off the top).
• Right shift: every bit moves toward a less significant position (one index lower). The bit at index 0 is dropped. This divides the value by 2 (discarding any remainder).

Note the asymmetry. A left shift can lose data off the top: whatever bit was sitting at bit 7 before the shift is gone for good, and that's called overflow. A right shift always loses whatever bit was sitting at bit 0 — that's the remainder of the division by 2, discarded rather than rounded. Shifting by more than one position is just this same single-position move applied that many times in a row: shifting left by 3 is "shift left by 1," done three times.

Example 1 — Left shift by 1, no overflow

Take A = 0110 1101 (109, Lesson 2's running example) and shift it left by one position:

bit index:        7  6  5  4  3  2  1  0
A (before):        0  1  1  0  1  1  0  1
A << 1 (after):    1  1  0  1  1  0  1  0

Every bit moved one position left; a new 0 filled bit 0. The bit that fell off the top was A's old bit 7, which was 0 — nothing was lost. A << 1 = 1101 1010 = 218, and sure enough 109 × 2 = 218.

Example 2 — Left shift by 1, with overflow

Take C = 1010 1100 (172) and shift it left by one position:

bit index:        7  6  5  4  3  2  1  0
C (before):        1  0  1  0  1  1  0  0
C << 1 (after):    0  1  0  1  1  0  0  0

This time the bit that fell off the top was a 1 — real information is gone, not just a coincidental zero. C << 1 = 0101 1000 = 88. Doubling 172 "should" give 344, which doesn't fit in 8 bits at all (255 is the widest 8-bit value); 88 is what's left after that top bit is discarded: 344 − 256 = 88.

Example 3 — Right shift by 1, discarding the remainder

Take A = 0110 1101 (109) again and shift it right by one position:

bit index:        7  6  5  4  3  2  1  0
A (before):        0  1  1  0  1  1  0  1
A >> 1 (after):    0  0  1  1  0  1  1  0

Every bit moved one position right; a new 0 filled bit 7. The bit that fell off the bottom was A's old bit 0, which was 1 — that bit is simply gone. A >> 1 = 0011 0110 = 54. 109 ÷ 2 = 54.5, and the discarded bit was exactly that missing 0.5: shifting right always rounds down, never to the nearest value.

Example 4 — Shifting by more than one position

A shift by more than one position is the same single-position move, repeated. Take Example 1's result, A << 1 = 1101 1010 (218), and shift it left twice more to get A << 3 overall:

step      binary        decimal   bit lost off the top
A         0110 1101     109       —
A << 1    1101 1010     218       0  (Example 1 — no overflow)
A << 2    1011 0100     180       1  — overflow
A << 3    0110 1000     104       1  — overflow

Each row is one more single-position left shift of the row above it. Two of those three shifts dropped a real 1, so the final decimal value isn't simply 109 × 8 = 872 — 872 doesn't even fit in 8 bits. The true result is whatever's left after each of those bits fell off the top in turn, and 872 mod 256 = 104 matches the bit-by-bit result exactly.