The Algebra Of Two’s Complements

Explaining the mathematics behind the standard way of representing negative numbers in binary.
→ [preprint] ←  Keywords: #binary-representation #twos-complements #modular-arithmetic

How computers represent negative numbers is usually taught at time when students are not familiar with modular arithmetic, which means it has to be taught as gospel: the students learn what the rules are, but not why they are as they are. Moreover, those students that go on pursuing paths that lead them to learn modular arithmetic, have by that time bigger things on their plate to be worrying about binary representations… So this is one thing that students usually graduate without understanding. Additionally, I could could not find any decent explanation of the mathematics of two’s complements. And so I wrote one myself.

Status of the preprint: finished except (optional) section 2, that aims to provide some of the needed results of modular arithmetic. Otherwise it is complete—which means readers already familiar with that branch of mathematics will be able to read it without loss.

May 14, 2024. Got feedback? See the contact page.

*   *   *

Update history

August 13, 2024. Added a conclusion with a challenge for the reader, and changed the workflow of section 3, to start with the goal of having the most significant bit reserved for sign, and only then proceed to explain the need for modular arithmetic. Also did small improvements on the rest of the text. The version prior to this update can be retrieved here.

August 5, 2024. (Important!) Corrected three significant typos:

  • First, after tables 1 and 2, on page 2, the description of the “quick rule” to compute the additive inverse of a number, given its two’s complements representation switched “right” with “left” and vice-versa.

  • Second, in table 6 (page 8), there is a \(0\) carry bit right of the \(y\), but this is wrong: that carry bit can also be \(1\)—and thus, it must be represented as an arbitrary bit.

  • Third, in §5, when dealing with extending the representation of negative numbers, from \(n\) to \(n + 1\) bits, where it was written “two’s complement representation of a negative integer \(a\)” (page 9), \(a\) was replaced with \(-a\), which is the correct version.

In addition, some other minor clarifications where introduced. The version prior to this update can be retrieved here.

May 26, 2024. Corrected typos and improved the explanation of when (and when not) does modular addition coincide with regular integer addition. The version prior to this update can be retrieved here.