1s Complement

This representation extends the idea from sign-and-magnitude. In sign-and-magnitude, we negate a number by flipping the left-most bit. Extending this negation to flipping the all the bits and not just the left-most bit, we get 1s complement representation.

Similar to sign-and-magnitude, we also need to specify the number of bits we need to use.

Representation

Informally, the idea is to negate a number by flipping all the bits instead of just the left-most bit.

More formally, we can represent 1s complement using the formula:

-x = 2ⁿ-x-1

How do we read the formula? Consider a number 12. If we are using 8 bits 1s complement number, we can represent -12 as _the binary representation of -12 = 2⁸-12-1 = 243.

The left part of the formula above

-12 = 2⁸-12-1

comes from the formula above by substituting n = 8 and x = 12. Thus, n is the number of bits and x is the value that we want to negate.

But we did say that the idea is to flip all the bits to negate a number. Let's check if that's correct.

It is as if by magic, the result is indeed as if we flipped all the 8 bits!

Properties

Sign Bit

Since we flip all the bits, it means we also flip the left-most bit. Furthermore, since positive numbers should still be represented as a standard unsigned binary, we find that the left-most bit will actually work similar to a sign bit. This can actually also be shown using the formula, but we omit it.

Range

Given that the left-most bit acts like a sign bit, it means that the largest positive number can be represented as 0111...11. This gives us the same largest value as sign-and-magnitude which is (+2^n-1-1)₁₀.

But what about the smallest negative? We at least know that we can flip all the bits from the largest positive to obtain 1000...00. For obvious reason, it is (-2^n-1-1)₁₀.

Now, can we actually get a smaller number? Unfortunately, no. Consider the smaller (-2^n-1)₁₀. The representation of this in 1s complement should be the bit flip of (+2^n-1)₁₀. But (+2^n-1)₁₀ is 1000...00. Flipping the bits, we get 0111...11. However, this value is positive!

So, we can conclude that there is no smaller number than (-2^n-1-1)₁₀. As such, the range is the same as sign-and-magnitude which is (2ⁿ-1)₁₀. Note that we are still missing one number. In fact, we can see that the same problem of redundant 0 is also present in 1s complement.

Arithmetic

The formula for 1s complement actually reveals a very interesting property. Consider any number x. We can show that x + (-x) is equal to 0.

This hints at the possibility that we can perform addition with negative numbers without doing anything special. We can check this by enumerating all possibilities. But that can take long, so we will skip the formal proof.

Addition

Instead, we will show the intuition behind this. We show by starting from the number 0 and keep on incrementing by 1. To simplify the discussion, we keep track of the numbers generated by 4 bit 1s complement.

What is interesting about this pattern is that as we increment the number, we reach the largest number (e.g., +7 with binary 0111) and then we go into the smallest number (e.g., -7 with binary 1000). Ignoring this jump, notice that incrementing the binary by 1 will increment the value by 1 regardless of whether we are in the positive or negative domain.

Extending this further, what is addition except repeated addition by 1! So, it shows that we can actually just perform addition normally and just keep the number of bits in the result to be fixed (i.e., if we start with 4 bits, we should also end with 4 bits).

As we are fixing the number of bits, we can now look at what happen if we increment -0 by 1. Incrementing the binary 1111 by 1, we should technically get 10000. After keeping it at 4 bits, we get 0000. So, incrementing -0, we get +0. As such, we can represent this as a line (or rather, a circle). In this circular representation, an increment is simply following the arrow. So, if we begin at +0 and keep on incrementing, we will get to +7. Incrementing +7 will give us -7.

Now, the circular representation shows a certain problem with performing addition. If we start with a negative number x (e.g., -1) and we add a positive number y such that x + y > 0 (e.g., add 3), then we actually encounter 0 twice! The problem here is that by performing repeated increment, we are actually missing an increment due to redundant 0. So, we need to check if we actually cross this point. If we do, then we add 1 into the result to correct the deficit from redundant 0. Remember, we cross this point if the number of bits in the result should have been 1 more than n.

Overflow

Unfortunately, there can still be a subtle problem with this. Consider the 4 bits 1s complement number again. What happen if we do (7 + 7)?

1
2
3
4

0111
0111
---- + 
1110

Notice how 1110 is not actually 14 since we are using 1s complement. Instead, it is actually -1. How can two positive numbers result in a negative number? The problem here is that the result would have been outside of the range of the 1s complement used.

So, we have to check if the result makes sense. This check is called the overflow check. Fortunately, there is a simple rule to check for overflow. First, there are two ways overflow can happen:

1. Two positive numbers result in a negative number.
2. Two negative numbers result in a positive number.

So, the rule is:

• Check that two operands have the same sign.
• Check that the result have different sign than the operands.

Arithmetic Rule

Combining all the rules, we get the following pseudo-code assuming that both A and B have the same number of bits. We further assume that the function num_bits return the actual number of bits.

1
2
3
4
5
6
7
8
9

# input : number A in 1s complement
#         number B in 1s complement
# output: number C = A + B
C := A + B                           # binary addition
if num_bits(C) == num_bits(A) + 1 do # crossed the line
  C := C + 1
end
check_overflow(A,B,C)                # overflow rule above
C := truncate(C)

Subtraction

We can perform subtraction using 1s complement rather easily because our addition is simply binary addition. The following equation summarises how we can subtract two numbers.

A - B ≡ A + (-B)

Remember, we can simply flip all the bits to obtain -B.

1
2
3
4

0 011     +3
0 100     +4
----- +   -- +
0 111     +7

1
2
3
4

0 101     +5
1 010     -5
----- +   -- +
1 111     -0

1
2
3
4
5
6
7

 1 101     -2
 1 010     -5
 ----- +   -- +
10 111     -7
     1
 ----- +
 1 000

1
2
3
4
5
6
7

 1 100     -3
 1 000     -7
 ----- +   --- +
10 100     -10
     1
 ----- +
 0 101