寻找异或后置位数量最多/最少的非空子集

我有一组N个数字（N<100，规模较小），每个数字包含B个比特位（B极大，至少百万级）。需要找到一个非空子集，使得子集内数字异或后的B位整数的置位（1的数量）最多；同时也要找到置位数量最少的非空子集。

示例说明 #

举个简单例子：假设N=3个64位数字，二进制形式如下：

A := 0111000010111000110011011110101100100001000011110100001111000100  (30 bits set)
B := 1011100011010110000100111101100011010100110000110101100111011110  (34 bits set)
C := 0011111110111010011101001111000010101110111110101000100011010011  (37 bits set)

它们的异或结果如下：

A^B   := 1100100001101110110111100011001111110101110011000001101000011010  (34 bits set)
A^C   := 0100111100000010101110010001101110001111111101011100101100010111  (35 bits set)
B^C   := 1000011101101100011001110010100001111010001110011101000100001101  (31 bits set)
A^B^C := 1111011111010100101010101100001101011011001101101001001011001001  (35 bits set)

这个例子里，置位最多的子集是{C}（37个置位）；最少的是{A}（30个置位）。如果A的置位更多，那{B,C}（31个置位）就会成为最少的情况。

现有思路的瓶颈 #

• 暴力解法：需要遍历2^N -1种组合，每次异或操作要O(B*N)时间，就算缓存中间结果，总复杂度还是O(2^N * B)，对于当前N和B的范围完全不可行。
• 中间相遇法：把集合分成两半，分别计算2^(N/2)个中间异或和，再对其中一半做高维近邻搜索找匹配或补码。但就算忽略搜索的可行性和耗时，复杂度还是O(2^(N/2)*B)，依然难以处理。
• 高斯消元法：把数字看作0-1向量找线性相关性，但N个高维向量（B极大）几乎不可能线性相关，没法得到全0异或和。不过如果已知最大/最小异或和，倒是能用这个方法找到对应的子集。

关键转化观察 #

对于元素数量为偶数的子集，将所有元素按位取反后，子集的异或和和原子集完全相同（每个比特被翻转偶数次）；对于元素数量为奇数的子集，取反后的子集异或和是原结果的按位取反——这意味着最大解和最小解可以相互转化：

• 如果找到针对最大置位的算法，就能推导最小置位的解法：
  1. 若真实最小解是奇数元素子集，只需翻转所有比特后搜索新的最大解，结果取反就是最小置位。
  2. 若真实最小解是偶数元素子集，就逐个猜测其中一个元素，在剩余元素中搜索最大置位的奇数子集，遍历所有N种猜测后取最小值。
  3. 最后比较奇偶候选结果，得到真实的最小置位解。

需求 #

现在已经没有新的思路，希望得到可行的解法——如果无法得到最优解，能给出和真实最优解置位占比非常接近的近似解也可以接受。

内容的提问来源于stack exchange，提问作者Dillon Davis