CLR cover
Previous problem

Problem 102: Run-length Encoding

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

The binary representation (expansion) of a positive integer $x$ is denoted by $r(x)\in\{\sa{0},\sa{1}\}^*$. The run-length encoding of a word $w\in\sa{1}\{\sa{0},\sa{1}\}^*$ is of the form $\sa{1}^{p_0}\sa{0}^{p_1}\cdots \sa{1}^{p_{s-2}}\sa{0}^{p_{s-1}}$, where $s-2\geq0$, $p_i$s are positive integers for $i=0,\dots,s-2$ and $p_{s-1}\geq0$. Value $s$ is called the run length of $w$.

In the problem we examine the run length of the binary representation of the sum, the difference and the product of two integers.

Let $x$ and $y$ be two integers, $x\geq y\gt 0$, and let $n$ be the total run length of $r(x)$ and $r(y)$. Show that the run lengths of $r(x+y)$, $r(x-y)$ and $r(x\times y)$ are polynomial with respect to $n$.