Prove that for every $n$, the binary representation of $n + 1$ contains exactly one bit that flips from $0$ to $1$

289 Views Asked by At

I know since $n$ is a binary representation it can be represented $ \sum_{i = 0}^{p}b_{i}\cdot 2^{i}$, where $b_{i}\in \{0,1\}.$

I have the intuition for this problem, i think. If $n$ is odd then the right most bit that is a $0$ will be $1$ ONLY. If $n$ is even then only $b_0 = 1$ since $n+1$ will now be odd and you divide an odd by $2$ it's remainder will be $1$. I just have trouble formalizing this and proving there is exactly ONE BIT that flips from $0$ to $1$.

1

There are 1 best solutions below

0
On

The statement needs some clarification. First: I guess it means that going from $n$ to $n+1$ one (and only one) bit flips from $0$ to $1$. Second: consider for example $n=3$, we have $11 \to 100$... so, to make the statement true, we either need to imagine that binary numbers have an infinite number of zeroes on the left, or that we are working with fixed length binary numbers (and $n$ is smaller than the biggest number).

Granted the above, let $j$ be the position of the rightmost zero of the binary representation of $n$ (positions numbered from the right, starting from $0$).

Then we have, in binary, $j$ (perhaps zero) consecutive ones on the right, followed by a zero, followed by additional (perhaps none) arbitrary bits on the left. That is

$$\begin{align} n: *****&0\underbrace{11 \cdots 1}_{j \text{ ones}}\\ n+1: *****&1\underbrace{00 \cdots 0}_{j \text{ zeroes}} \end{align} $$

where the placeholders on the left are unmodified.

Then, indeed, one and only one bit (that in position $j$) flips from $0$ to $1$, while $j$ bits flip from $1$ to $0$, and the rest are not modified.