1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I suppose that you mean that there is exactly one bit that flips from $0$ to $1$ when between the binary representation of $n$ and the binary representation of $n+1.$ $\endgroup$ – md2perpe Mar 10 at 17:14
  • 3
    $\begingroup$ Hint: divide the binary representation of number $n$ in three parts $ A | 0 | B$ where $B$ (perhaps empty) consists of all ones. Show that $n+1$ takes the form $A | 1 | C $ where $C$ consists of all zeroes. $\endgroup$ – leonbloy Mar 10 at 17:18
  • $\begingroup$ yes, so $\exists !b_{i}$ $\endgroup$ – neet Mar 10 at 17:21
  • $\begingroup$ @leonbloy That's worth turning into an answer. $\endgroup$ – rogerl Mar 10 at 17:42
  • $\begingroup$ can you elaborate a bit more @leonbloy $\endgroup$ – neet Mar 10 at 17:57
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.