Number of setbits(x or y) + Number of setbits(x and y) = m. Is there any way to solve this equation, to find relation between x and y?

Question

I have been asked one question in the HackerEarth coding platform, to find pairs x and y from the arrays that satisfy the above equation.

Answer 1

There is a useful property of setbits:

setbits(x | y) + setbits(x & y) == setbits(x) + setbits(y)

This is true because the OR and the AND pair sort of "redistribute" the bits without changing the total number of set bits. For example consider 1-bit numbers:

x y   x&y x|y
0 0    0   0
0 1    0   1
1 0    0   1
1 1    1   1

On every row, x&y and x|y together have as many set bits as x and y together.

With that, the problem is really equivalent to finding pairs of numbers that add up to m (this has been covered in other questions on this website), and the setbits aspect is just a distraction.