Last Updated on April 11, 2024

In my last post I made a promise. We talked about IEEE 754 Standard and some other things.

One thing we talked about was Two’s Complement. We used that as a valid thecnique for handling binary integers. By that post we already know that it works like a charm, like magic.

I like magic ticks but when it’s related to our area there’s no magic at all, only science and a bunch of very smart people that made all of this possible. Because of that, I really enjoy to go deeper and, try to, understand what’s under the hoods.

This article is the one that fulfills this promise. Today, we will get deeper and really understand why and which concepts are behind of Two’s Complement.

Recap Two’s Complement

Before diving into the trick revelation, let’s recap what Two’s complement is and why it is important.

The Definition

Two’s complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with an equivalent negative value, using the binary digit with the greatest place value as the sign to indicate whether the binary number is positive or negative. It is used in computer science as the most common method of representing signed (positive, negative, and zero) integers on computers,[1] and more generally, fixed point binary values. When the most significant bit is 1, the number is signed as negative; and when the most significant bit is 0 the number is signed as positive.
Source: wikipedia

In short, two’s complement allows us to handle signed numbers in binary more easily.

Our 3-bit machine

Here is a table of numbers that can be represented in our 3-bit machine in Two’s complement.

Numbers starting with zero are the positive ones, just like unsigned numbers. Like, 011₂ really represents 3₁₀.

The most significant bit turns the number into negative. In order to get a decimal representation of a binary number in two’s complement we can apply the formula below.

-2^(n-1) * b(n-1) + ... + 2¹ * b1 + 2⁰ * b0

Where b(n-1) is the most significant bit. If we take 101₂ as an example then we have:

-2² x 1 + 2¹ x 0 + 2⁰ x 1 = -4 + 0 + 1 = -3 (as described in the table)

Playing a bit… with bits

In two’s complement we can convert a positive binary number into a negative binary number and vice versa using the same procedure that is described as following:

1. invert all bits;
2. add 1 to the result from last step.

Conversions

Converting 3 to -3

We get 3₁₀ that is 011₂ and then:

1. invert all bits resulting into 100₂
2. add 1₂ to 100₂ resulting into 101₂.

Our final result is 101₂ which is, indeed, -3₁₀.

You can also get 3 from -3. You can apply the same process.

Trick Revealed

Modular Arithmetic 101

Modular arithmetic is a arithmetic system for integers where numbers reset when reaching a certain value – known as modulus.

A familiar application of this arithmetic is the 12-hour clock. Every twelve hours the time gets reset. If it’s 11:00,
then 2 hours later it will be 1:00. Indeed, 11 + 2 is equal to 13 which in modulus 12 it becomes 1 – because we reset whenever it reaches to the modulus, 12 in this case. We say that 13 and 1 are congruents modulus 12.

Math Notation

1 ≅ 13 (mod 12)

The modulus, in this case, is 12. Whenever the number reaches 12, it gets reset. That’s why 13 (mod 12) = 1.

If you’re paying attention enough, you’ll find out that 25 (mod 12) is also congruent to 1.

Think about it:

13 = (12 + 1) // one cycle completed plus 1
25 = (24 + 1) // two cycles completed plus 1

Every complete cycle turns the clock to zero, so adding one to the result is just adding one to zero.

I hope it didn’t confuse that much. We will see more details in the next section.

Congruence

a and b are said to be congruent modulo n if there’s an integer k such that:

a - b = kn, n > 1

This relation can be rewritten as:

a = kn + b.

It looks familiar to what we saw in the last section. We defined 25 congruent to 1 in modulus 12. Below, we have such a congruence applied to the relation.

25 = 12k + 1.

That’s exactly what we did with the 24 + 1. 24 is just 12 x 2. So, 24 + 1 = 12 x 2 + 1 – our k is 2.

How it applies to Two’s complement

The whole thing is about cycles. We get an infinite set of numbers and make it to fit into a smaller set. Any integer number modulus 12 will never be less than zero neither greater than eleven.

Numbers in modulus n have the range: 0 to n-1.

It’s important to observe how the things get complimented. In modulus 12, to get from 1 to 11 we can either:

• subtract 2;
• add 10.

To get from 1 to 10 we can either add 9 or subtract 3. If you put it into a table you’ll eventually reach to the following relation:

Subtract "a" from a number "b" modulus n is equivalent to add n - a.

Hence, b - a (mod n) <=> b + (n - a) (mod n)

Illustrating, subtract 2 from 1 (mod 12) is the same as adding 10 (the same as 12 - 2). Subtracting 3 is the same as adding 9 (the same as 12 - 3).

Applying the concepts

Our machine has only three bits so we have a small range of numbers that we can represent. Thinking about unsigned numbers, only for a moment, we could represent from 0₁₀ to 7₁₀.

What about the eight? We never get there. Eight, in binary, is 1000₂. But, you know, our machine deals only with three bits, which means the MSB, in this case, will be thrown away, leading us back to 000₂.

It looks very familiar – the number reset aftear reaching a certain value.

Hopefully, you got the idea here. Our machine is modulus eight. So, subtracting a number a from any number b in our machine is the same as adding:
8 - a.

To subtract 2 from any any number we just need to sum (8-2). Remember, we are operating in modulus eight. In binary, it’s basically adding 1000₂ – 010₂.

As an example, let’s say we want subtract 2 from 3. We would do: 011₂ + (1000₂ – 010₂). Performing the operation 1000₂ – 010₂ will result into 110₂, that’s -2₁₀ in two’s complement. So the operation becomes 011₂ + 110₂ hence the result of the whole operation is 001₂.

A closer look

Why does 1000 – 010 work turning 2 into -2?

Well, to perform this subtraction we would need to do something like:

It’s the same as we do in decimal operations. We keep borrowing from the next column. It may sound confusing since we’re not accostumed to binary system.

Let’s simplify things with a math trick. Instead of just get straight and do the subtraction as we did in the last step we will sum zero to this expression, but in a clever way. We will subtract 1 from the minuend then add 1 to the difference.

Instead of 1000₂ – 010₂ we will have (1000₂ – 1₂) – 010₂ that is equivalent to 111₂ – 010₂ (1).

Solving (1) is very simple as illustrated below. We no longer need to borrow anything.

Now we can balance our expression by adding 1₂ to the difference: 101₂ + 1₂ which is equal to 110₂.

We did it – haven’t you seen?

We just did Two’s Complement. Look, we need to perform 1000₂ – 010₂, which is the same as (1000₂ – 1₂) – 010₂ + 1₂. Simplifying we have: 111₂ – 010₂ + 1₂.

The 111₂ – 010₂ flips out the bits. In fact, every subtraction where the minuend has all the bits set to 1 will flip out the subtrahend bits.

a - b = !b

a, has all bits set to 1

After this operation we only need to add one to the difference. That is the second step in the Two’s Complement algorithm.

Performing an operation from scratch

Let’s practice what we just learned performing the operation 3₁₀ – 2₁₀ from scratch.

011₂ – 010₂
=> 011₂ + (1000₂ – 1₂ – 010₂ + 1₂)
=> 011₂ + (111₂ – 010₂ + 1₂)
=> 011₂ + (101₂ + 1₂)
=> 011₂ + 110₂ = 1001₂

As mentioned before, we throw the carry out bit so the result of this operation is indeed 001₂ that’s equivalent to 1₁₀, the expected result.

Summary

In this article we dicussed the Two’s Complement approaching why and how it works. Two’s Complement plays a critical role on the matter of math operations using electronic curcuits. It’s is fundamental to understand better how chips like RAMs and CPUs can work.

Concepts like this empowers you to really understand how the machine works in deeper levels. It might be important if you need to implement something closer to hardware, write a programming language or even do some bitwise.

I plan to bring more low-level posts so we can better understand the machine. So keep in touch, we have some fun things to discuss.

That’s all. See ya!

References

• https://math.stackexchange.com/questions/1920772/why-twos-complement-works
• https://en.wikipedia.org/wiki/Modular_arithmetic

We want to work with you. Check out our "What We Do" section!