The FlipBits tree

28 Views Asked by At

Take a number, say $n=99_{10}$. Express it in binary, $11000111$. Now flip the bits, $0011100$ and discard leading $0$'s: $11100 = 28_{10}$. Continue until $0$ is reached: $(99,28,3,0)$. Here's a representation of the path, with $\Rightarrow$ meaning flip bits, and $\rightarrow$ meaning discard leading $0$'s:

$$99_{10} = 11000111 \Rightarrow 0011100 \rightarrow 11100 (=28_{10}) \Rightarrow 00011 \rightarrow 11 (=3_{10}) \Rightarrow 00 \rightarrow 0 \;.$$

Another example: $(10,5,2,1,0)$:

$$10_{10}= 1010 \Rightarrow 0101 \rightarrow 101(=5_{10}) \Rightarrow 010 \rightarrow 10(=2_{10}) \Rightarrow 01 \rightarrow 1 \Rightarrow 0 \;.$$

One can view the reductions in a FlipBit Tree:


          FBitTree


Q. Is there a characterization of those numbers that will each take $k$ steps to reach zero?

So $5$, $9$, and $99$ each take $3$ steps, whereas $10$ and $100$ both take $4$ steps. Perhaps a characterization in the $0/1$-runs structure of $n$'s binary representation?

I'd also be interested in any nontrivial structural properties of the FlipBits tree you might observe.

1

There are 1 best solutions below

1
On BEST ANSWER

Each time you apply the operation the number of runs of the same bit decreases by $1$ because you remove the leading run. $99_{10}=1100111_2$ so it will take three applications to get to $0$. $1100000111100011111001_2$ has seven runs, so will take seven applications to get to $0$. Each number in your tree can be extended by flipping its bits and putting some number of $1$s on the front. If $n$ has $k$ bits, flipping the bits gives $2^k-n-1$, then putting $p\ 1$s on the front adds $2^{p+k}-2^k$ so you get $2^{p+k}-n-1$ for a total.