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) = 2^{n}. And in base 2 positional notation 2^{n} would be written 100…00 (a one followed by *n* zeros).

Let x ∈ ℕ, 2^{n} > x ≥ 0. Define the 2’s complement of x as 2^{n} – x if x ≠ 0. When x = 0 its 2’s complement is 0. So x + (2^{n} – x) = 2^{n} and 2^{n} – (2^{n} – x) = x.

0 < x < 2^{n-1} ⇒ 0 > -x > -2^{n-1} ⇒ 2^{n} > 2^{n} – x > 2^{n-1}.

2^{n} > x > 2^{n-1} ⇒ -2^{n} < -x < -2^{n-1} ⇒ 0 < 2^{n} – x < 2^{n-1}.

Note that 2^{n-1}, like zero, is its own complement.

If we want half of the bit patterns (2^{n} ÷ 2 = 2^{n-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 2^{n-1} – 1.

If we have the representation of a negative integer then it’s easy to compute the corresponding negative integer. Let 2^{n-1} < 2^{n} – x < 2^{n}. Remove sign bit: 2^{n} – x – 2^{n-1} = 2^{n-1} – x. Then -2^{n-1} + (2^{n-1} – x) = -x.

**Addition of two negative integers**

Let x,y ∈ ℕ, x ≠ 0, y ≠ 0. To show that -x + -y = -(x + y), assume x < 2^{n-1}, y < 2^{n-1}, x + y < 2^{n-1}. Then (2^{n} – x) + (2^{n} – y) = 2^{n} + (2^{n} – (x + y)). Discarding the 2^{n} bit leaves 2^{n} – (x + y).

**Addition of a positive integer and a negative integer**

0 < y < x < 2^{n-1} ⇒ 0 < x – y < 2^{n-1}.

x – y = x + -y ≡ x + 2^{n} – y ≡ x – y (discarding the 2^{n} bit).

0 < x < y < 2^{n-1} ⇒ 0 < y – x < 2^{n-1} – x < 2^{n-1}.

x – y ≡ x + 2^{n} – y = 2^{n} – (y – x).

x – y < 0 ⇒ x – y ≡ 2^{n} – |x – y| = 2^{n} – -(x – y) = 2^{n} – (y – x).

**Sign Extension**

2^{n} > 2^{n} – x ≥ 2^{n-1}.

*m* additional bits.

Sign extend: 2^{n} – x + Σ(i = 0 to m-1, 2^{n+i}).

Prove: 2^{n+m} – x = 2^{n} – x + Σ(i = 0 to m-1, 2^{n+i}).

2^{n+m} – x – (2^{n} – x + Σ(i = 0 to m-1, 2^{n+i})) = 2^{n+m} – Σ(i = 0 to m-1, 2^{n+i}) – 2^{n} = 2^{n+m} – 2^{n+m} = 0.