求解按位 XOR 和 ADD 方程

Question

自然可以异或两次取回原来的值。如果原始值是掩码的一部分怎么办？

编码：

e[i] = c[i] ^ (c[i] + c[i-1])

假设：起始值c[-1] = 0，^表示按位异或

命令式 C 形式：

void encode(byte *p, int len)
{
    byte prev = 0;
    for (auto i = 0; i < len; i++)
    {
        auto byt = p[i];
        p[i] = byt ^ (prev + byt);
        prev = byt;
    }
}

我如何创建一个解码步骤来从 e => c 反转它？

我已经 simplified/clarified（阅读：更改）根据我从您的回答中学到的知识来回答这个问题！使用与 DanL 类似的步骤，从原始方程式开始：

e[i] = c[i] ^ (c[i] + c[i-1])

e[i] ^ c[i] = c[i] ^ (c[i] + c[i-1]) ^ c[i]
e[i] ^ c[i] = c[i] + c[i-1]
c[i] = e[i] ^ c[i] - c[i-1]
c[i] ^ c[i] = (e[i] ^ c[i] - c[i-1]) ^ c[i]
0 = e[i] ^ c[i] ^ c[i] - c[i-1] ^ c[i]
0 = e[i] - c[i-1] ^ c[i]
c[i-1] ^ c[i] = e[i]
c[i-1] ^ c[i] ^ c[i-1] = e[i] ^ c[i-1]
c[i] = e[i] ^ c[i-1]

???

现在，查看原始编码 - 第一个字节将始终为零 (= c[i] ^ (c[i] + 0))。所以是的，必须在集合中丢失一个字节。

Answer 1

在循环的每次迭代中，您都在有效计算

c_i = e ^ ( p + c_(i-1) )

如果你想反转循环然后给定一个 c_i 你需要计算 c_(i-1)

然而，正如你所说，异或两次可以让你回到原来的值，而异或是一个交换运算，所以如果你用 e 对上面的等式进行异或，我们就会得到

c_i ^ e = e ^ ( p + c_(i-1) ) ^ e

简化为

c_i ^ e = p + c_(i-1)

然后两边拿p给你

(c_i ^ e) - p = c_(i-1)

因此在你的 "reversal" 循环中

你想要代码

c = (c ^ e) - p

编辑：在上下文中看到带有代码的修订问题后，我认为这是不可能的，因为我相信 mix 函数有效地将 len 字节数组映射到 len-1 字节数组。

我相信这是因为以下论点：

将未混合的数组称为unmixed，应用mix函数后的混合数组称为mixed

mixed[0] = unmixed[0] ^ (0 + unmixed[0])  //Remember prev = 0 initially

因此混合[0] = 未混合[0] ^ 未混合[0] = 0

因此混合数组的第一个字节将始终为 0。

mix 函数不会增加或减少数组的大小，因此我们最终得到第一个元素为 0 的 len 字节数组。

因此我们有效地将 space 个 len 字节数组映射到 len-1 个字节数组。

如果这是完全可逆的，我们将能够将 n 字节数组压缩为 n-1 字节数组，然后将 n-1 字节数组压缩为 n - 2 字节数组，依此类推。

如果我们以单字节数组为例，那么我们看到 mix 只生成一个元素为 0 的数组，你怎么知道它是之前 256 个可能的未混合数组中的哪一个？

求解按位 XOR 和 ADD 方程

Solving bitwise XOR and ADD equation

bitwise-operators

logical-operators

equation-solving

bitwise-xor