姬長信(Redy)

算法-有多少个4个数字集,使得它们的xor等于…


我有两个非负整数x和y,它们都最多具有30位(因此它们的值大约为10 ^ 9).

我想计算多少组4个数字{a_1,a_2,a_3,a_4}使得a_1 a_2 = x和a_3 a_4 = y且所有这4个数字的xor等于0.

解决这个问题最快的算法是什么?

我能想到的最快的方法是将xor方程重新排列为a_1 xor a_2 = a_3 xor a_4.

然后,我可以计算O(x)中左侧的所有值和O(y)中右侧的所有值,因此整个算法在O(x y)中运行.