**Yue LI**

**Date:** May 7, 2023

The x86 unsigned multiplication instruction MUL multiplies RAX with some quadword and stores the result in RDX:RAX. The overflow flag OF and carry flag CF are set if the high-order bits of the result, which are stored in RDX, are non-zero. The notion of overflow applicable to the MUL instruction is therefore that multiplication of two -bit (unsigned) integers has a result that is longer than bits. Taking into account that MUL actually uses bits to store the result of multiplication of two -bit numbers, in this blog we ask and answer a different overflow question: is it possible that multiplying two n-bit unsigned integers and the result is longer than 2n bits?

We shall answer negatively, and prove the following Proposition.

Since an all-ones, like 11111111111, is the largest -bit unsigned integer for every , if we can show that two -bit all-ones multiply and the result is no more than bits, then the Proposition easily follows.

Our proof for the Lemma is inductive, but before examining the formal arguments, let's warm up by looking at some particular cases.

Below we show that the Lemma holds for . We shall use sum of powers of 2 to denote an unsigned binary integer, then e.g. 1111 is . Equation 1 shows that has 1 bit.

Next, when building Equation 2 we use Equation 1 (as underlined).

Equation 2 shows that has 4 bits. Next, when building Equation 3 we use Equation 2.

Equation 3 shows that has 6 bits. Next, when building Equation 4 we use Equation 3.

Equation 4 shows that has 8 bits. Next, when building Equation 5 we use Equation 4.

Equation 5 shows that has 10 bits. Next, when building Equation 6 we use Equation 5.

Equation 6 shows that has 12 bits.

Based on Equations 1–6, it is reasonable to conjecture that for all ,

Note that on both sides of Equation 7 the powers of 2 are in descending order, so that the right hand side is instantiated by when , by when and by when , and so on.

Based on how we progress from Equation 1 to 6, we have the following scheme of progression from the square of sum up to -th power of 2, to the square of sum up to -th power of 2.

Based on the facts that Equation 1 holds, and that for all , if Equation 7 holds then Equation 8 holds, we can justly conclude that our conjecture that for all Equation 7 holds, is true. This proves our Lemma. Then the Proposition follows.

This document was generated using the LaTeX2HTML translator Version 2019.2 (Released June 5, 2019)

The command line arguments were:

`latex2html -no_navigation -split 0 MUL.tex`

The translation was initiated on 2023-05-07