Signed Int: One's Complement

Introduction

One's complement is another way to represent signed ints. It's not the most obvious way to represent signed values (SM would be more obvious), and in fact, it has all the problems that SM has. But it leads to a representation that is very useful: two's complement.

We'll abbreviated one's complement as 1C.

To understand 1C, you need to understand what it means to flip a bit. Flipping bits was introduced in the notes on SM.

We want to define flipping all of the bits of an N bit number. To flip all the bits means to do bi = bi' for 0 <= i <= N-1. bi' means flipping bit i.

Hopefully, the meaning of flipping all bits is obvious.

We'll use the notation of ~ to mean "flip all bits". Think of it as an operator (in fact, it is the "C" language operator for flipping all bits). Thus, ~B is B with all bits flipped.

Sometimes I will say "negating" a bit, which is the same as flipping a bit. It is also the same as the logical negation of that bit. It is also the same as subtracting the bit's value from 1.

Base Ten to One's Complement (1C)

Here's the algorithm to convert base 10 (decimal) to one's complement (1C) using N bits. From now on, we'll include the number of bits when talking about representations. Thus, I won't say, write the number in 1C, but in 1C using N bits, where I (usually) specify N.

  1. Ignore the minus sign, and convert the base ten value to N bits, unsigned.
  2. If there is a minus sign, flip all bits of the N bit number from step 1. Otherwise, step 1 has the correct answer.
It should be easy to represent numbers in 1C. I suggest trying the following exercise. Using 4 bits, write all numbers from -7 to +7 in 1C.

If you're wondering whether there are some numbers that can't be represented in 1C using N bits, that's good. There are some numbers that can't be represented. The algorithm above only works for numbers that can. Below, we'll explain which values can be represented in 1C using N bits.

One's Complement (1C) to Base Ten

Converting 1C to base 10 isn't that hard either. It's the reverse process.
  1. If the most significant bit is 1, flip all bits. If the MSb is 0, go to the next step.
  2. Convert the result to base 10. This value should be non-negative.
  3. Add a negative sign if the sign bit of the original 1C representation was 1.

How Many Values?

Whether you flip just the sign bit (as in SM), or flip all bits (or in 1C), each positive number still maps to a unique negative number, except possibly 0. Half the representations still have 1 as the most significant bit, and the other half still have 0.

The number of positive representations (including positive 0), given N bits, is 2N-1, just like SM.

The number of negative representations (including negative 0), given N bits, is 2N-1, just like SM.

Similar Problems

Both SM and 1C have two representations of the value zero. They both have a positive zero representation and a negative zero representation. The hardware to handle two zeroes is more complicated, and if there's a representation that can avoid this, it would be preferable.

You still have problems adding values correctly in 1C as you did in SM. However, it turns out that the addition is somewhat closer to correct with one's complement (but still incorrect).

Negation

To peform the operation of negation in 1C, i.e. given value X, compute -X (in 1C), you flip all bits. This operation clearly allows --X to equal X (flipping bits twice gets you back to the same original bit). Thus, -X = ~X (that is, negating X in 1C is equivalent to flipping all bits of X).

Chart

Number of Bits Number of Values Min Value Max Value
16 216 - 1 -(215 - 1) 215 - 1
32 232 - 1 -(231 - 1) 231 - 1
N 2N - 1 -(2N-1 - 1) 2N-1 - 1

Notice this chart is exactly the same as SM. In particular, even though there are 2N possible bitstring patterns for N bits, there are only 2N - 1 values (because there are 2 representations for zero).

Conclusion

Both SM and 1C have the same range of values. Both have the same minimum and maximum value. Both have two representations for zero. Both representations can't use unsigned int addition hardware to do addition. Both representation schemes make use of the sign bit. That is, you can tell whether a number is positive or negative (except zero) using the sign bit.

Even though both are similar, most people would find 1C more difficult to understand than SM, because it seems like "more work", i.e., negating requires flipping all bits instead of flipping just the sign bit.

However, we primarily study 1C because it leads into two's complement, which is yet another signed int representation, and is discussed in the next section.

Web Accessibility