setbits Number of setbits(x or y) + setbits Number of setbit

Question

在HackerEarth编码平台上有人问我一个问题，从满足上述方程的数组中找出x和y对。

Answer 1

setbits有一个有用的性质:

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

这是正确的，因为"或"one_answers"与"对排序是"重新分配"的。不改变设置位总数的位。例如考虑1位数字:

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

在每一行上，x&y和x|y加起来的集位数等于x和y加起来的集位数。

有了这个，这个问题实际上相当于找到加起来等于m的数字对(这已经在本网站的其他问题中讨论过)，而setbits方面只是分散注意力。