Probably the most illuminating way of calculating the number of possible bit patterns of a bit string of length n is combinatorially by the counting principle: 2 × 2 × 2 × … × 2 (n occurrences of 2) = 2n. And in base 2 positional notation 2n would be written 100…00 (a one followed by n zeros).
Let x ∈ ℕ, 2n > x ≥ 0. Define the 2’s complement of x as 2n – x if x ≠ 0. When x = 0 its 2’s complement is 0. So x + (2n – x) = 2n and 2n – (2n – x) = x.
0 < x < 2n-1 ⇒ 0 > -x > -2n-1 ⇒ 2n > 2n – x > 2n-1.
2n > x > 2n-1 ⇒ -2n < -x < -2n-1 ⇒ 0 < 2n – x < 2n-1.
Note that 2n-1, like zero, is its own complement.
If we want half of the bit patterns (2n ÷ 2 = 2n-1) to represent negative integers then it’s natural to let the first n-1 bits represent zero and the positive integers from 1 to 2n-1 – 1.
If we have the representation of a negative integer then it’s easy to compute the corresponding negative integer. Let 2n-1 < 2n – x < 2n. Remove sign bit: 2n – x – 2n-1 = 2n-1 – x. Then -2n-1 + (2n-1 – x) = -x.
Addition of two negative integers
Let x,y ∈ ℕ, x ≠ 0, y ≠ 0. To show that -x + -y = -(x + y), assume x < 2n-1, y < 2n-1, x + y < 2n-1. Then (2n – x) + (2n – y) = 2n + (2n – (x + y)). Discarding the 2n bit leaves 2n – (x + y).
Addition of a positive integer and a negative integer
0 < y < x < 2n-1 ⇒ 0 < x – y < 2n-1.
x – y = x + -y ≡ x + 2n – y ≡ x – y (discarding the 2n bit).
0 < x < y < 2n-1 ⇒ 0 < y – x < 2n-1 – x < 2n-1.
x – y ≡ x + 2n – y = 2n – (y – x).
x – y < 0 ⇒ x – y ≡ 2n – |x – y| = 2n – -(x – y) = 2n – (y – x).
Sign Extension
2n > 2n – x ≥ 2n-1.
m additional bits.
Sign extend: 2n – x + Σ(i = 0 to m-1, 2n+i).
Prove: 2n+m – x = 2n – x + Σ(i = 0 to m-1, 2n+i).
2n+m – x – (2n – x + Σ(i = 0 to m-1, 2n+i)) = 2n+m – Σ(i = 0 to m-1, 2n+i) – 2n = 2n+m – 2n+m = 0.
Yell Algebra 