Bits and integers: 2's complement, overflow, sign extension

This course starts with numbers, because a computer sees only bits: 0 or 1. An integer, a letter, an instruction are all the same string of 0s and 1s. The meaning depends on how you read that string. A question from this page is certain on the midterm: read a pattern in four ways, convert a number to 2’s complement, add two numbers and justify with the rule whether overflow occurred.

Golden rules:

1. The pattern carries no meaning, the representation does. 1100 0110 is 198 as unsigned and -58 as 2’s complement.
2. In 2’s complement the weight of the MSB is negative: -128 in 8 bits.
3. -X = invert + 1.
4. Overflow occurs only when two numbers with the same sign are added and the result has the opposite sign.
5. Sign extension: when widening, copy the MSB, do not fill with 0.

Bits and positional value

With $k$ bits you can write $2^k$ different patterns. 8 bits: 256 patterns. In an unsigned integer the weight of each bit is a power of 2. The rightmost bit is the LSB (b0, weight 1), the leftmost is the MSB (b7 in 8 bits, weight 128).

weight:  128  64  32  16   8   4   2   1
bit:       1   0   0   1   1   1   0   1     = 128+16+8+4+1 = 157

Decimal → binary

There are two methods. Division: divide by 2, write the remainder, continue until the quotient is 0, read the remainders from bottom to top. Subtracting powers (faster): subtract the largest power of 2 that fits and write 1 in that column.

214 → 214-128=86 → 86-64=22 → 22-16=6 → 6-4=2 → 2-2=0
the 1s: 128, 64, 16, 4, 2  →  1101 0110 = 0xD6

Binary ↔ hexadecimal

One hex digit is exactly 4 bits. When going from binary to hex, group in fours from the right and complete the left group with 0s.

10 1111 0111   →   0010 1111 0111   →   0x2F7
0x2F7 = 2·256 + 15·16 + 7 = 512 + 240 + 7 = 759

PITFALL · grouping from the left. For 1011101, if you write 1011|101 from the left you get B5, which is wrong. From the right: 101|1101 → 0101 1101 = 0x5D.

Signed numbers: four representations

There are three historical ways of writing negative numbers. In all of them, if MSB = 0 the number is positive and the value is the same as unsigned. The differences show up only when MSB = 1.

For general $k$ bits:

$\text{2's complement: } -2^{k-1} \;\ldots\; 2^{k-1}-1 \qquad \text{SM and 1's: } -(2^{k-1}-1) \;\ldots\; 2^{k-1}-1$

Example: 0x9C = 1001 1100.

Quick check: 2’s complement value = unsigned - 256. 156 - 256 = -100.

Why does everyone use 2’s complement?

Because the adder circuit gives the right result without caring about the sign at all. $5 + (-5)$: 0000 0101 + 1111 1011 = 1 0000 0000, and when the 9th bit is discarded, 0000 0000. There is a single zero and the adder is the same as for unsigned. The LC-3 and almost all computers use 2’s complement.

2’s complement: taking the negative

Recipe: write the positive, invert all the bits, add 1.

+77   = 0100 1101
invert = 1011 0010
+1    = 1011 0011   = -77 = 0xB3
check: -128 + 32 + 16 + 2 + 1 = -77

Shortcut: start from the right, copy as is up to the first 1 (including that 1), and invert every bit to its left. 0010 1000 (40) → 1101 1000 (-40).

Note: the most negative number has no positive counterpart. In 8 bits, -128 = 1000 0000; invert + 1 gives 1000 0000 again.

Sign extension

When you move a number into a wider field (for example a 5-bit offset into a 16-bit register), you copy the MSB to the left. If it is positive, 0s are added; if negative, 1s. The value does not change.

In 16-bit hex, negative numbers start with F: -13 = 0xFFF3, -6 = 0xFFFA. When you write ADD R1, R1, #-1 in the LC-3, the 5-bit 11111 is widened to 16 bits this way (weeks 7-8).

PITFALL · filling with 0. If you turn 10110 into 00010110, it becomes 22. A negative number turned positive. In sign extension there is a single rule: copy the MSB.

Addition, subtraction and overflow

2’s complement addition is ordinary binary addition: from right to left, carry the carries upward. 1+1 = 0 carry 1, 1+1+1 = 1 carry 1. The 9th bit spilling out of the MSB is discarded.

There is no separate circuit for subtraction: $A - B = A + (-B)$.

The overflow rule

If the result does not fit in the range of $k$ bits, overflow occurs. The way to detect it is to look at the signs:

• If (+) + (+) = (−), overflow.
• If (−) + (−) = (+), overflow.
• In (+) + (−) overflow never occurs.

The exam sentence: “Overflow occurs only if both operands have the same sign and the result has the opposite sign.” The equivalent test in hardware: if the carry into the MSB differs from the carry out of the MSB, overflow.

Worked example 1: 01010101 + 00101010

   0101 0101    ( 85)
 + 0010 1010    ( 42)
 -----------
   0111 1111    (127)   two positives, positive result → no overflow

Worked example 2: $A = 10010110$, $B = 00110010$, $A - B$ = ?

A  = 1001 0110   = -106
B  = 0011 0010   =  +50   → -B: invert 1100 1101, +1 → 1100 1110 (-50)

    1001 0110   (-106)
  + 1100 1110   ( -50)
  -----------
  1 0110 0100   → the 9th bit is discarded → 0110 0100 = +100

The true answer $-106 - 50 = -156$ does not fit in 8 bits. The two numbers added (A and -B) are negative, the result is positive: overflow. The carry into bit 7 is 0, the carry out is 1.

PITFALL · confusing carry-out with overflow. 11110000 + 00100000 = 1 00010000. A 1 spilled out but the result is 16, which is correct (-16 + 32). In unsigned addition, carry-out means “the result is large”; in 2’s complement it is not an indicator of overflow. The opposite also happens: in 01101100 + 00110001 there is no carry-out, but there is overflow.

PITFALL · looking at the wrong number in A − B. When applying the overflow rule, look at the sign of -B, not of B. Because that is the number being added.

How many bits are needed?

Common mistakes