Adding positive binary patterns

Binary addition works from right to left, just like column addition in denary. First make the two patterns the same width and align their least significant bits on the right. Each column produces a sum bit to write in that column and may produce a carry bit for the next column to the left.

The result 10 for 1 + 1 means "write 0 here and carry 1". It does not mean writing a digit 2, because binary has only the digits 0 and 1.

Worked example: add two positive 8-bit patterns

Add 0010 1101 and 0001 0111.

Starting at bit 0, the rightmost bit:

Read the written bits from bit 7 to bit 0:

  0010 1101
+ 0001 0111
-----------
  0100 0100

As a check, the supplied values are 45 + 23 = 68, and 0100 0100 represents 68.

Use the same column method on this nearby pair.

Overflow and available bits

Bit width is part of the question, not a formatting choice. An 8-bit register has room for exactly eight stored bits. A carry between columns is normal; it becomes evidence of unsigned overflow only when it leaves an extra bit beyond the register's left edge.

Worked example: a ninth bit appears

Treat both patterns as positive unsigned 8-bit values:

  1110 0100
+ 0011 1001
-----------
1 0001 1101

The exact sum is the 9-bit pattern 1 0001 1101. Only eight bits are available, so the register can retain only 0001 1101; that stored pattern does not represent the exact sum. Overflow has occurred because the result needs nine bits.

Signedness matters too. Suppose two positive 8-bit two's-complement patterns are added:

  0100 0000   (+64)
+ 0100 0000   (+64)
-----------
  1000 0000

There is no ninth carry bit, but the exact positive result is +128. It would need the 9-bit signed pattern 0 1000 0000; the 8-bit pattern 1000 0000 has an MSB of 1 and is not positive in two's complement. This is still overflow. Therefore, "a carry happened" is not a complete definition: always use the stated width and signedness.

Overflow does not automatically mean a program crashes. A particular system might retain a wrapped bit pattern, raise a flag or handle the condition in another way. The defining fact is that the exact value cannot be represented in the available bits.

Now separate the full result from the bits that the register can retain.

Logical binary shifts

A binary shift moves every bit in a fixed-width pattern left or right by a stated number of positions. Bits that move beyond an end are discarded; they do not wrap around to the other end.

For an 8-bit unsigned pattern:

• a logical shift left by n moves the bits n places left, discards bits leaving the left edge and inserts n zeroes on the right;
• a logical shift right by n moves the bits n places right, discards bits leaving the right edge and inserts n zeroes on the left.

Worked example: shift 0010 1101

Each shift by one position corresponds to a factor of 2. Therefore, a left shift by n corresponds to multiplication by 2^n only when the exact result fits the available bits. A logical right shift of an unsigned value gives the whole-number result of division by 2^n because any bits leaving the right edge are discarded.

Keep both results at exactly eight bits in the following check.

Arithmetic binary shifts

Arithmetic shifts are used with signed two's-complement patterns. The bit width stays fixed, but the fill rule for a right shift changes so that the sign is preserved.

If the original MSB is 0, an arithmetic right shift inserts 0s. If the original MSB is 1, it inserts 1s. It does not "always add ones".

Worked examples: arithmetic right

The signed values are supplied so that the operation, rather than conversion, stays in focus.

0011 0100  (+52)
  right 1 -> 0001 1010
  right 2 -> 0000 1101  (+13)

The original sign bit is 0, so zeroes enter on the left.

1101 0000  (-48)
  right 1 -> 1110 1000
  right 2 -> 1111 0100  (-12)

The original sign bit is 1, so ones enter on the left. Every existing bit still moves; the sign bit is not held apart in a fixed box.

Arithmetic left

An arithmetic left shift uses the same bit movement as a logical left shift: bits move left, bits leaving the left edge are discarded, and 0s enter on the right. The difference is interpretation. The pattern represents a signed value, so the exact doubled value must still fit the signed bit width.

For example, signed 8-bit 1110 0110 represents -26:

1110 0110  (-26)
  left 1 -> 1100 1100  (-52)

The exact result fits, so this arithmetic left shift is valid without overflow.

[DIAGRAM: asset_name: Logical and arithmetic right shifts; asset_slug: 2_1_4_2_1_5_binary_arithmetic_shifts_and_overflow__diagram_01; recommended_method: image_gen; description: Monochrome three-row comparison of the 8-bit pattern 10110010, showing logical right shift by 2 as 00101100 with zero fill and arithmetic right shift by 2 as 11101100 with copies of the original MSB; in both cases the rightmost bits 10 are discarded.]

Apply one left shift and one right shift, keeping the signed interpretation in view.

Shifts, overflow and final decisions

Use this order whenever you apply or explain a shift:

1. Record the fixed bit width and whether the pattern is unsigned or signed.
2. Identify the direction and whether the shift is logical or arithmetic.
3. Move every bit the stated number of positions, use the correct fill rule and discard bits leaving the pattern.
4. Keep the required width, then decide whether the exact mathematical result is representable. If it is not, overflow has occurred.

Worked example: unsigned logical-left overflow

An unsigned 8-bit register holds 0111 1000, representing 120, and applies a logical shift left by two.

Exact mathematical result: 120 x 4 = 480
Full binary result:         1 1110 0000
Stored 8-bit result:          1110 0000

The exact result needs nine bits, so the stored 8-bit pattern cannot represent 480. This is overflow.

Worked example: signed arithmetic-left overflow

An 8-bit signed register holds 0101 0000, representing +80, and applies an arithmetic shift left by one.

Bit operation:              0101 0000 -> 1010 0000
Exact mathematical result:  +80 x 2 = +160

The exact positive value +160 cannot be represented in signed 8-bit two's complement; it would need an additional leading sign bit. The stored result begins with 1, so it would be interpreted as negative rather than +160. Overflow has occurred even though the bit discarded from the left was 0.

For the integer right shifts in this lesson, the result does not need a larger magnitude than the starting value, so overflow is a left-shift risk. Do not use "a 1 was discarded" as the universal test: the reliable test is whether the exact result fits the stated width and signedness.

Use all four decision steps on a new signed value.