找到最小位数以区分一组二进制数的算法

Question

假设我们有K个二进制数(每个都是相同的长度).我们需要找到所需的最少位数(不需要是连续的)来唯一地识别这些K二进制数.例如100,110可以区分1位(在第二位置).111,110,101需要2比特来区分.

Answer 1

我们可以将这些二进制视为一组线性方程。因此，例如，如果我们有这些二进制：1111、1100、1001，我们可以将它们表示如下：

x1 + x2 + x3 + x4 = y1
x1 + x2 + 0  + 0  = y2
x1 + 0  + 0  + x4 = y3

从这里，我们意识到，我们可以使用高斯消元法来简化这些方程，以消除额外的变量（在上面的例子中，它是x1）。约简的结果将是一组 K 个不同的变量，我们删除一个额外的变量以获得原始问题的结果。