You need to find all x for given y such that f(x)=y.
Explanation:
Let us consider a number x. And suppose that we divide it by two exactly ‘a’ times, and then we would be left with some number ‘b’.
Then the result would be (b*(b-1))/2 + b*((2^a)-1).
As this equation is increasing for a fixed ‘a’ we can use binary search over ‘b’ to get values.
This can be also solved by finding solutions of above quadratic equation.
Consider a number in binary form. Let the number is 1101000
Then the f(1101000) = 110100+11010+1101+f(1101)
f(1101) can be calculated easily as it is odd.
Now we see pattern. Consider b=1101 then f(1101000) = b.4+b.2+b+f(b).
Remember b is odd and hence f(b)=b*(b-1)/2.
Now the summation of terms can also written in this form: b[1+2+4] = b[7] = b[(2^3)-1].
Hence when number is divisible by exactly 3 times we write it as b*[2^3-1].
And this can be generalised to b*[2^d-1] when number is divisible by 2, d times.
