Complement
In computers, the representation and manipulation of negative numbers is often performed using complements.
Two’s Complement form
This is the unanimous choice to represent numbers in Binary.
The 2’s complement form is a very popular convention that maps sequences of bits to integers in the range from to .
Ex: In two’s complement, the bit sequence represents the number
The property that makes two’s complement convenient is that if any sequence S of $n$ bits is interpreted both as a binary number $b$ and as a two’s complement number $t$, then $b \equiv t (\bmod 2^n)$.
2’s Complement Trick
From CS241E, to find the 2’s complement encoding of a small negative number, take the positive unsigned number, invert its bits, and add 1 to the result binary number. Ex:
- (unsigned)
- Flipping all the bits:
- Add 1:
We can also do the same in to go from signed negative to unsigned positive numbers.
Proof: ??
Used to get the negative of a signed binary number.
→ This is what is widely used nowadays
To negate a value:
- Take the complement of all bits
- Add 1
Other way to think about it from CS241E:
- Take the biggest bit, and make that negative. The idea is to represent the same as
Another way is Subtraction by Addition, see Binary Number.
Also see the Sign Extension shortcut, which is super important for Sign Extension shortcut, which is super important for ECE222.
One’s Complement
Used for unsigned numbers.
8’s Complement, 9’s Complement
Calculated by subtracting the number from 888888 / 999999
R’s Complement (Radix Complement)
9’s complement 1’s complement
The complement of a complement returns the original number
Signed magnitude → Left-most bit indicates sign
Conversion between number systems
Convert 53 to binary
Decimal to binary is very straightforward.