Before showing you the function that we came up with to reverse a number, we have to define two functions. First, $\text{len}_b(x)$, which gives the number of digits in $x$ when written in base $b$.

$$ \text{len}_b(x) = \big\lceil \log_b(x + 1) \big\rceil $$Then, we have $\text{at}_b(x, i)$, which gives the digit at index $i$ of $x$ when written in base $b$. This is zero-indexed and $i=0$ refers to the least significant digit. For example $\text{at}_{10}(123, 0) = 3$

$$ \text{at}_b(x, i) = \left\lfloor \frac{\lvert x \rvert}{b^i} \right\rfloor \text{ mod } b $$Here, $\text{mod}$ is an operator, not the equivalence class. Now, here's our definition of reverse,

$$ \text{rev}_b(x) = \sum_{i = 0}^{\text{len}_b(x) - 1} \text{at}_b(x, i) \cdot b^{\text{len}_b(x) - i - 1} $$Let's break this down. The $\Sigma$ can be described as a "loop". We loop through all of the valid indices $i$ of the digits in $x$. For each index $i$, we take the digit in $x$ at that index and "place" it in a new number at a new index $\text{len}_b(x) - i - 1$. Notice, this new index is exactly the index of this digit in the reversed number.

What's even cooler is that we can translate our definition of
$\text{rev}$ *back into code*. Here's a snippet using Python,

Let's test it out here to verify that it it works:

Awesome! The first expression shows that $12345$ reversed when written in base $10$ comes out to $54321$, which is what we expected! Then we see that $\text{rev}(37001_8, 8) = 10073_8$, as expected. Finally we see that $\text{rev}(\text{deadbeef}_{16}, 16) = \text{feebdaed}_{16}$.

Even though this is over 10 times slower than the naive string-reversal approach, it's still pretty cool that this can be done using only binary operations.

Next, we'll talk about sorting the digits of an integer.