Note that in two's complement, non-negative numbers have an implicit infinite number of leading 0's, and negative numbers have an implicit infinite number of leading 1's.
For example,
0 = 00000000 = 00000000 00000000
( = 0_{10} )00010 = 00000010 = 00000000 00000010
( = 2_{10} )11110 = 11111110 = 11111111 11111110
( = -2_{10} )01101 = 00001101 = 00000000 00001101
( = 13_{10} )10011 = 11110011 = 11111111 11110011
( = -13_{10} )
Prove: -x = x + 1
[In our examples, we will assume that integers are 8 bits long, but the proof applies to binary integers of any length (e.g., 16 bits, 32 bits, 64 bits).]
Let
x
represent the one's complement ofx
.Note that in two's complement, the definition of
-1
is11111111
(the result of subtracting1
from0
).Note that
x + x = 11111111 = -1
. This is true because for every0
inx
, the corresponding bit inx
is1
, yielding a sum bit of1
, and for every1
inx
, the corresponding bit inx
is0
, again yielding a sum bit of1
. For example:00001101
13+ 11110010
one's complement of 13----------
11111111
Since
we can add one to both sides and getx + x = -1
x + x + 1 = 0
Now, by definition,
so, substitutingx + (-x) = 0
x + (-x)
for 0 in our previous result, we haveorx + x + 1 = x + (-x)
orx + 1 = (-x)
(-x) = x + 1
addu
, subu
, and
addiu
all ignore overflow (unsigned integer
calculations); the "sign bit" gives
an extra digit's worth of positive numbers we can express.