Two's complement
Two’s complement represents a signed integer in a fixed number of bits by giving the top bit negative place value: in 8 bits, the top bit is worth −128 and every other bit its ordinary positive value. A positive number is plain binary. A negative number’s encoding can be derived mechanically: invert every bit, then add one. Addition is ordinary unsigned binary addition, modulo the width — the circuit never knows or cares which numbers are "negative".
When it is the right choice
This is how essentially every processor represents a signed integer; there is no competing scheme in ordinary use to choose instead (sign-magnitude and ones’ complement exist, but are not what any reader’s own integers are doing).
How it works
- A non-negative number is its plain binary representation.
- To encode a negative number, invert every bit of its magnitude’s binary form, then add one.
- To decode, read the top bit as worth −(2^(width−1)) and every other bit its ordinary positive place value.
- Addition is plain unsigned binary addition on the bit patterns, wrapping silently modulo 2^width.
Worth noticing
- 127 + 1, both valid 8-bit values, wraps silently to −128 — the processor raises no error; the bits simply mean something unintended.
- −128 is representable in 8 bits but +128 is not — so negating −128 (invert, add one) produces −128 again, the one value that is its own negation.
- The sign bit is not a separate flag bolted onto a magnitude — it is an ordinary bit with its own (negative) place value, which is exactly why addition does not need to treat it specially at all.
Cost
- Best
- O(1)
- Average
- O(1)
- Worst
- O(1)
- Extra space
- O(1)