binary number maximum 1's

Question

If we are given a binary number we have to find the number of maximum ones that can be obtained if we can invert( $ 1\rightarrow0, 0\rightarrow1$ ) exactly $x$ number of bits in one iteration. We can do as many iterations as we like.

$\text{Here we can reverse 3 bits at a time so }x=3;\\ 100000\\ 111100\\ 110010\\ 111111\\ $

Answer 1

Obviously, if the binary length of your number is $n$, you won't be able to achieve the goal if $x=n$. So we'll assume that $x<n$.

Let us first prove the following lemma:

You cannot turn all zeroes into ones if the initial number of zeroes is odd and $x$ is even.

Proof: Suppose that in $x$ selected bits you have $x_1$ zeroes and $x-x_1$ ones. After the switch the number of zeroes decreases by $x_1$ and increases by $x-x_1$. So the net change in the number of zeroes is:

$$x-x_1-x_1=x-2x_1$$ The point is: if $x$ is even, the number of zeroes changes by an even number and if you start with an odd number of zeroes, you will never reach the number with all ones.

end of lemma proof

But you can get pretty much close:

Base Case: Suppose that you have at least two zeros in the binary representation of your number. WLOG, we can assume that the first two bits are zeros (same logic applies to a pair of zeroes wherever they are). So pick the first zero and $x-1$ bits starting from third and switch them. After that, pick the second zero and the same set of $x-1$ bits starting from third and switch them.

Obviously, all bits starting from the third are unchanged, but the first two zeroes are now ones. The procedure described in this case is guaranteed to reduce the number of zeroes by two. If you have an even number of zeroes in the beginning you will turn all of them into ones and you are done.

If you have an odd number of zeroes in the beginning you can bring down the number of zeroes to a single one. All other bits are ones by now.

If $x$ is odd, pick any number of ones and turn them into zeroes. Now you have an even number of zeroes and by applying "base case" you will be able to switch the number into all bits equal to one.

In case when $x$ is even and you have an odd number of zeroes in the beginning you will be able to get the number with a sinle zero but you won't be able to turn it into one. One zero has to remain.

So you can either reach a number with a single zero (if the starting number of zeroes is odd and $x$ is even) or no zeroes at all (in all other cases).