Two's complement is a clever way of storing integers so that common math problems are very simple to implement.
To understand, you have to think of the numbers in binary.
It basically says,
- for zero, use all 0's.
- for positive integers, start counting up, with a maximum of 2(number of bits - 1)-1.
- for negative integers, do exactly the same thing, but switch the role of 0's and 1's and count down (so instead of starting with 0000, start with 1111 - that's the "complement" part).
Let's try it with a mini-byte of 4 bits (we'll call it a nibble - 1/2 a byte).
0000
- zero
0001
- one
0010
- two
0011
- three
0100
to 0111
- four to seven
That's as far as we can go in positives. 23-1 = 7.
For negatives:
1111
- negative one
1110
- negative two
1101
- negative three
1100
to 1000
- negative four to negative eight
Note that you get one extra value for negatives (1000
= -8) that you don't for positives. This is because 0000
is used for zero. This can be considered as Number Line of computers.
Distinguishing between positive and negative numbers
Doing this, the first bit gets the role of the "sign" bit, as it can be used to distinguish between nonnegative and negative decimal values. If the most significant bit is 1
, then the binary can be said to be negative, where as if the most significant bit (the leftmost) is 0
, you can say the decimal value is nonnegative.
"Sign-magnitude" negative numbers just have the sign bit flipped of their positive counterparts, but this approach has to deal with interpreting 1000
(one 1
followed by all 0
s) as "negative zero" which is confusing.
"Ones' complement" negative numbers are just the bit-complement of their positive counterparts, which also leads to a confusing "negative zero" with 1111
(all ones).
You will likely not have to deal with Ones' Complement or Sign-Magnitude integer representations unless you are working very close to the hardware.
"yep base-10 is what I mean"
In that case, yes, they can be extended to base-10 in several ways, though they aren't nearly as useful as in binary.
One idea is that &
, |
, etc. are the same as doing arithmetic mod-2 to the individual binary digits. If a
and b
are single binary-digits, then
a & b = a * b (mod 2)
a ^ b = a + b (mod 2)
~a = 1-a (mod 2)
a | b = ~(~a & ~b) = 1 - (1-a)*(1-b) (mod 2)
The equivalents in base-10 would be (note again these are applied per-digit, not to the whole number)
a & b = a * b (mod 10)
a ^ b = a + b (mod 10)
~a = 9-a (mod 10)
a | b = ~(~a & ~b) = 9 - (9-a)*(9-b) (mod 10)
The first three are useful when designing circuits which use BCD (~a
being the 9's complement), such as non-graphing calculators, though we just use *
and +
rather than &
and ^
when writing the equations. The first is also apparently used in some old ciphers.
Best Answer
There are many reasons, here are some:
For those and other reasons most processors have bit shift and/or rotation instructions as well as other logic instructions (and/or/xor/not).
Historically multiplication and division were significantly slower as they are more complex operations and some CPUs didn't have those at all.
Also see here: Have you ever had to use bit shifting in real projects?