javascript - 给定函数 H(A, B) = (A ^ B) ^ ((A & B) << 1) 的输出 C，如何编写一个给定 C 和 B 输出 A 的函数？

Question

假设a和b是无符号整数，请考虑以下函数：

function H(a, b) {
    var c = (a ^ b) ^ ((a & b) << 1);
    return c
};

这个函数的描述可以在 NORX 规范中找到（链接在这个页面）。

我需要实现（在Javascript中）的反向功能。H也就是说，给定c和b，函数需要输出a。

该规范提供了一种用于反向函数的算法（假设v[i]表示i整数的第 - 位v）：

a[0] = c[0] XOR b[0];
a[1] = (c[1] XOR b[1]) XOR (a[0] AND b[0]);
...
a[i] = (c[i] XOR b[i]) XOR (a[i-1] AND b[i-1]);

但我不知道如何实现它。

我尝试了以下函数（注意参数是 UintNArrays 的元素，所以我们假设它N是 8 或 16 或 32）：

function revH(c, b) {
    var x = (c ^ b) >>> 0; var a = x;

    for (var i = 1; i < N; ++i) {
        x0 = (c ^ b) ^ ( (a >>> i) & (b >>> i )); 
        a = (a & ~(0x1 << i)) | ((x >>> (N-i)) << i);
    };
    return a
};

但是这个函数不正确（它不会输出正确的结果）。如何实现的反向功能H？

标签： javascriptalgorithmbit-manipulation

Answer 1

另一个基于位方程的版本，从位 0、位 1 到位i

c ₀ = a ₀ ⊕ b ₀
c ₁ = a ₁ ⊕ b ₁ ⊕ a ₀ b ₀
...
c _i = a _i ⊕ b _i ⊕ a _i-1 b _i-1

借助 ⊕ 属性，根据这些方程从b和c中找到a

a ₀ = c ₀ ⊕ b ₀
a ₁ = c ₁ ⊕ b ₁ ⊕ a ₀ b ₀
...
a _i = c _i ⊕ b _i ⊕ a _i-1 b _i-1

这允许我们编写一个与等式完全相同的小程序（此处为 32 位）

const int N = 32;

unsigned revH(unsigned c, unsigned b) {
     unsigned a = (c ^ b) & 1;     // bit 0
     for(int i=1 ; i<N ; i++) {    // bit i
          a |= ((c ^ b) & (1<<i)) ^ (((a & b) & (1<<(i-1))) << 1);
     }
    return a;
}