0

I'm trying to simplify the following expression (I hope to be able to write it in a nicer form) but I cannot. For $m \in \mathbb{N}$ and $n \in \mathbb{N}$, $l(m)$ is defined as

$$l(m) = 2 m - (m \bmod 2^{n-1}).$$

Can the above be expressed in a simpler or more compact form?

Thanks in advance.

Michael Albanese
  • 99,526
MikeL
  • 627

1 Answers1

1

Let $m = a_k2^k + a_{k-1}2^{k-1} + \dots + a_12^1 + a_02^0$, then

\begin{align*} 2m &= a_k2^{k+1} + a_{k-1}2^k + \dots + a_12^2 + a_02^1\\ (m \bmod 2^{n-1}) &= a_{n-2}2^{n-2} + a_{n-3}2^{n-3} + \dots a_12^1 + a_02^0. \end{align*}

Therefore

\begin{align*} &\ l(m)\\ &\\ =&\ 2m - (m \bmod 2^{n-1})\\ &\\ =&\ a_k2^{k+1} + a_{k-1}2^k + \dots + a_12^2 + a_02^1 - (a_{n-2}2^{n-2} + a_{n-3}2^{n-3} + \dots + a_12^1 + a_02^0)\\ &\\ =&\ a_k2^{k+1} + a_{k-1}2^k + \dots + a_{n-1}2^n + a_{n-2}2^{n-1} + \dots + a_12^2 + a_02^1\\ & -a_{n-2}2^{n-2} - a_{n-3}2^{n-3} - \dots - a_12^1 - a_02^0\\ &\\ =&\ a_k2^{k+1} + a_{k-1}2^k + \dots + a_{n-1}2^n + a_{n-2}(2^{n-1} - 2^{n-2}) + \dots + a_1(2^2 - 2^1) + a_0(2^1 - 2^0)\\ &\\ =&\ a_k2^{k+1} + a_{k-1}2^k + \dots + a_{n-1}2^n + a_{n-2}2^{n-2}(2 - 1) + \dots + a_12^1(2-1) + a_02^0(2 - 1)\\ &\\ =&\ a_k2^{k+1} + a_{k-1}2^k + \dots + a_{n-1}2^n + a_{n-2}2^{n-2} + \dots + a_12^1 + a_02^0\\ &\\ =&\ a_k2^{k+1} + a_{k-1}2^k + \dots + a_{n-1}2^n + 0.2^{n-1} + a_{n-2}2^{n-2} + \dots + a_12^1 + a_02^0.\\ & \end{align*}

In the language of binary, if $m = a_ka_{k-1}\dots a_1a_0$, then $l(m) = a_ka_{k-1}\dots a_{n-1}\color{red}{0}a_{n-2}\dots a_1a_0$.

Example: If $m = 94$ and $n = 5$, then

$$l(m) = 2(94) - (94 \bmod 2^{5-1}) = 188 - (94 \bmod 16) = 188 - 14 = 174.$$

In binary, $m = 1011110$ and $l(m) = 101\color{red}{0}1110$.

Michael Albanese
  • 99,526