When converting a negative integer into 2's-complement binary notation, one must first represent the magnitude, then complement the bits, then add 1. It then follows that one could determine the magnitude of a negative 2's-complement binary number by reversing this process: subtract 1 from the binary number and complement the bits.

It turns out that there is an easier way to do the same thing. Rather than subtracting 1 and complementing the bits, one can simply complement the bits and then add 1 (the same process used to form the binary number in the first place!). The proof below describes why this simpler conversion is equivalent.

Theorem:

Let x be some binary number.
Let comp(x) be the binary complement of x.

Then, comp(x - 1) = comp(x) + 1

Proof:

Let b = an n-bit unsigned binary integer, b₁ b₂ b₃ ... b_n

Let comp(b) = the complement of b, an n-bit unsigned binary integer c₁ c₂ c₃ ... c_n such that for i = 1..n,

    c_i = 1 if b_i = 0
    c_i = 0 if b_i = 1

That is, comp(b) is an n-bit unsigned binary integer, such that each bit in c is the opposite of the corresponding bit in b.

Note that the binary addition

    b₁ b₂ b₃ ... b_n   +   c₁ c₂ c₃ ... c_n

gives a sequence of n 1's

    1 1 1 ... 1

since there are 0's in comp(b) exactly where there are 1's in b, and there are 1's in comp(b) exactly where there are 0's in b.

The decimal value of the binary sequence of n 1's (0111...1) is one less than the value of the binary sequence of a 1 followed by n 0's (1000...0). The value of a 1 followed by n 0's is 2ⁿ, thus

    b + comp(b) = (2ⁿ - 1)

which rearranges to:

    comp(b) = (2ⁿ - 1) - b

Question: What is the value of comp(b - 1)?

    comp(b - 1) = (2ⁿ - 1) - (b - 1)

                = ((2ⁿ - 1) - b) + 1

                = comp(b) + 1

Thus, comp(b - 1) = comp(b) + 1