I was wondering, how would one go about performing 3's, 4's, ...,
compliment? I was reading about this briefly in my colleagues' advanced
mathematics book but did not have very long to study it.
I know about 1's and 2's compliment, and have never heard of any others
(3, 4, etc.)
1's and 2's complement are the special cases of diminished radix and
radix notation. You can represent any base in these notations (in
both of these cases you are using base 2).
Both notations were designed to handle negative numbers. A naive
approach to handling negative numbers might involve setting a
sign bit. This works well for written numbers where we just use
a negative sign, but in it's something of a pain to deal with.
It would be easier to handle negative numbers if the mechanism
that signaled a negative number was some how built in to the
arithmatic.
So, Diminished Radix Arithmetic:
1) represent the absolute value of number in the base
you're interested in, plus a sign digit, e.g.,
89 in base 4: 01121
2) subtract separately each digit from (base - 1),
otherwise known as the diminished (by one) radix.
Negative 01121 (base 4) => 32212
That's it. To check, let's add 01121 and 32212:
01121
32212
-----
33333
That looks weird, until you realize that the leading 3 means
that it's a negative number. If we went through the negation
process again of step 2, we'd wind up with zero.
You'll note that the leading digit must be either a 0 or the
(base-1) digit. If the base is 2, then you have the 1's complement
notation. It's still a little odd, because this notation lets you
have two ways to represent zero.
Radix Arithmetic:
1) represent the absolute value of number in the base
you're interested in, plus a sign digit, e.g.,
89 in base 4: 01121
2) subtract the number from the base raised to the
power of the number of digits, e.g.:
100000 - 01121 (base 4) => 32213
(if the number was zero to begin with, let it be).
That's it. To check, let's add 01121 and 32213:
01121
32213
-----
100000
It looks like an extra digit sneaked in, but in reality we
didn't allow for an extra digit (remember that the lead digit
is the sign digit, and there's only those five positions
available).
So the carry of one "falls off the edge", and you wind up
with 00000, which is what we want. There's only one way to
represent zero, but you do wind up with one extra negative
number that doesn't have an equivalent positive number. If
the base you were using was 2, you'd be using 2's complement
notation.
Hope this helps. At the very least you have a lot of new
terms to use in Google.
