Given an integer n, find the largest positive integer that has the same number of 0s and 1s in its binary representation.
Example
For n = 5, the output should be
maxBits(n) = 6.5 = 1012, so the answer is 1102 = 6.
For n = 15, the output should be
maxBits(n) = 15.15 = 11112, so the answer is 11112 = 15.
Input/Output
- [time limit] 4000ms (js)
[input] integer n
Constraints:
0 ≤ n ≤ 1000[output] integer
An integer that has as many 0s and 1s as n
Solution
In order to get the greatest number with the same number of 0s and 1s, we need to sort the bits in a way, that all 1s come first, followed by the zeros. I think the fastest way is counting the zero and one digits and re-constructing the resulting number. Counting can be done quite easily with:
var z = 0, o = 0;
while (n > 0) {
if (n % 2)
o++;
else
z++;
n>>= 1;
}
Knowing the number of zeros and ones, the answer is given by
\[(2^{z+o}-1) - (2^z - 1) =2^{z+o} - 2^z = (2^o-1)\cdot 2^z\]
When we implement this for a code submission, we can use binary shifts for the power of two's and get
maxBits = n => {
for(z = o = 0; n ; n>>= 1)
n & 1 ? o++ : z++
return (1 << o) - 1 << z
}
That's quite small already, but we can do better by recursively removing zeros from within the number and by adding them afterwards by shifts to the end. So, how can we remove zeros from a binary number? When we look at the two least significant bits, we want to see the following reduction:
00 -> 0
01 -> 1
10 -> 1
11 -> 11
The problematic case is the last one, where we need to remember the one that gets shifted out. An idea is to add a one back to the front in this case. That means we shift out the least significant bit and bring a one back to the front. What happens if we add one to a binary number?
00 -> 001
01 -> 010
10 -> 011
11 -> 100
Okay, that means that an added 1 will propagate through the whole number. If we would chop off the last bit of that number as well, we'd need a way to get back to the chopped-off bit of the last step. When we or togehter these both steps, we have a result where only zeros get removed, until only one big block of 1s remains. Brought into a formula, this means the following expression removes a zero from a binary number:
\[(n >> 1) \;|\; ((n + 1) >> 1)\]
If we would loop over the bits of a number this way, we only need a way to determine, if we arrived at a block of ones. That can be implemented via a variation of a quite famous trick: check if a number is a power of two. That can be done easily with n & (n - 1) == 0. What we need here, is if the next number is a power of two, which means that we need to check (n + 1) & n == 0.
When we implement this solution, we must add a zero at the end of the number, for every zero we removed in the recursion. A first recursive attempt can then look like this:
_ = maxBits = n =>
((n + 1) & n) !== 0 ? (_((n >> 1) | ((n + 1) >> 1)) << 1) : n
That's only a few bytes less than the solution we originally implemented. However, we added loads of brackets. Also the explicit conditional test isn't needed. We can also remove the right shifts by divisions of two, since they come together under the binary OR-operator, which truncates decimal places. At the end, the left shift is removed by a multiplication of two, which leads to
_ = maxBits = n =>
n + 1 & n ? 2 * _(n / 2 | ++n / 2) : n