如何解码按位与运算编码的矩阵以还原对应的原始序列？

核心推导逻辑 #

我们可以利用按位与的运算特性直接推导原始序列，规则非常明确：

• 矩阵对角线值为-1的元素无意义，直接忽略
• 对于原始序列的第i个元素c_i，它等于第i行所有非对角线元素的按位或结果，公式为：

  c_i = OR of all T_ij where j ≠ i
  

实例验证 #

用你给出的矩阵测试：
矩阵非对角线内容：

行1：19, 0
行2：19, 0
行3：0, 0

计算结果：

• c_1 = 19 | 0 = 19
• c_2 = 19 | 0 = 19
• c_3 = 0 | 0 = 0
  和你给出的原始序列c = 19 19 0完全匹配。

特殊歧义说明 #

上述推导存在唯一解的前提是：原始序列中不存在某一个二进制位仅在单个元素中出现1的情况。如果某一位只有单个元素是1，其他全为0，那么所有和该元素相关的非对角线T_ij的对应位都是0，无法通过矩阵检测到该位的存在，会产生多解。
举个歧义例子：
原始序列为[3, 1, 1]，编码后矩阵所有非对角线元素对应位都是1，按上述方法推导会得到[1,1,1]，丢失了第一个元素的第二个二进制位（值为2）。如果需要消除这类歧义，需要额外补充约束条件，比如要求所有有效二进制位至少在两个序列元素中出现。

内容的提问来源于stack exchange，提问作者Ivan Petrushenko