If $n=(b_k,b_{k−1},...,b_1)_2$ where $b_i$ are the digits of n in binary, what is the binary expression of $n+1$?

Question

I have a curiosity.

If $n=(b_k,b_{k−1},...,b_1)_2$ where $b_i$ are the digits of n in binary, what is the binary expression of $n+1$? Is there a relationship that binds $n+1$ to $b_i$ (ie the digits of $n$ in binary)?

Answer 1

Let $n+1=(a_{k+1},a_k,a_{k−1},...,a_1)_2$ be the binary representation of $n+1$. Then

$$a_i = \begin{cases} b_i, & \text{if any of $b_{i-1},\ldots,b_1$ is zero} \\ 1-b_i, & \text{otherwise} \end{cases}$$

Therefore this formula works:

$$a_i=b_i+(1-2b_i)\cdot\prod_{j=1}^{i-1}b_j$$

for $1\le i\le k+1$. (Note the $k+1$, not $k$, since another digit may be added. That means that $b_{k+1}=0$, if it is needed. Also note that an empty product equals one.)

---

Doing this for base ten is harder, especially if I avoid logical functions like "if". Here is an answer that uses the sign function ($0$ for zero, $1$ for positive) as well as the binary mod operator (remainder after division).

If $n=(b_k,b_{k−1},...,b_1)_{10}$ and $n+1=(a_{k+1},a_k,a_{k−1},...,a_1)_{10}$ be decimal representations. Then

$$a_i =\left(1-\mathrm{sign}\left[\sum_{j=1}^{i-1}(9-b_i) \right] \right)\cdot[(b_i+1) \bmod 10-b_i]+b_i$$

Here is an easier one using the if function [$\mathrm{if}(l,a,b)$ yields $a$ if $l$ is true, $b$ if $l$ is false]:

$$a_i=\mathrm{if}\left(\sum_{j=1}^{i-1}(9-b_i)=0, (b_i+1) \bmod 10,b_i\right)$$

Here is another avoiding the mod but nesting if's:

$$a_i=\mathrm{if}\left(\sum_{j=1}^{i-1}(9-b_i)=0, \mathrm{if}(b_i=9,0,b_i+1),b_i\right)$$