假设我们给出了K不同的二进制数,每个都有长度N(N可以很大).是否有一种有效的算法来确定将这些数字相互区分所需的最小位数？
例如:
给定110和011,我们只需要检查第一个(或最后一个)位来区分它们,所以最小数量是1.
鉴于1000,0100,0010和0001,我们需要检查至少三位来区分,所以最少数量为3.
鉴于0000,0100,1000和1100,我们只需要检查的前两位,因此最小号码是2.
后续:输出要检查的相应索引.
编辑:假设这些二进制数表示为,...,.这个问题相当于找到最小的子序列,以便...,是不同的数字.a1[0,1,…,N-1]aK[0,1,…,N-1][i,j,…,m][0,1,…,N-1]a1[i,j,…,m]aK[i,j,…,m]
编辑：误解了问题，计划不起作用。
你想要做的是某种异或。但并不是简单地对所有数字进行异或。但是如果你能产生一个二进制数，当它是相关位时，它的值为 1；如果该位不相关，则它的值为 0。不相关位是指无论数字是什么都始终具有相同值的位：您不需要它来区分数字。例如：
11001
01001
10101
-----
11100
第一个和第二个位不相关，因为它们始终具有相同的值。
怎么做
为此，您需要从集合中计算两个二进制数。第一个是所有数字之间的逻辑或。仍然为 0 的位是无关的，很容易看出。第二个数字是该组所有数字的逻辑“与”。剩下的1位是无关紧要的，也很容易看出。现在，将这两个数字异或在一起。这就是你的结果。应用到前面的例子：
11001 | 01001 | 10101 = 11101
11001 & 01001 & 10101 = 00001
11101 ^ 00001 = 11100 // Here is your result, the first 3 bits are relevant