格雷码加法

Question

有没有已知的方法可以计算两个格雷码的加法（或减法），而不必将这两个格雷码转换为常规二进制数，执行二进制加法，然后将结果转换回格雷码？ 我已经编写了增量和减量功能，但加法和减法似乎文档记录更少，并且更难编写。

- Morwenn

---

在记忆中保持常规表示，进行操作，需要时再将其转换为格雷码，这样不是更容易吗？ - Marcos

@meaning-matters 嗯，我只处理无符号格雷码，因此，我不关心有符号的值。理想情况下，我希望格雷码溢出的方式与底层整数相同，但我非常怀疑这很容易实现。 - Morwenn

@Marcos 但我必须承认，这个问题更多地是出于好奇心而不是任何实际应用的驱动。 - Morwenn

你可以在Mathematica Stack Exchange或Computational Science Stack Exchange上获得更好的回答。期待你的答案。 - chux - Reinstate Monica

考虑到从二进制转换为格雷码非常容易，我相信将两个值转换为二进制，进行加减运算，然后再转换回格雷码会比遍历位更快，除非你是在 FPGA 或类似的设备上执行此操作。 - Speed8ump

Answer 1

在这份文档的第6部分中，有一个串行格雷码加法算法（直接复制；请注意，⊕表示异或）。

procedure add (n: integer; A,B:word; PA,PB:bit;
               var S:word; var PS:bit; var CE, CF:bit);
var i: integer; E, F, T: bit;
begin
   E := PA; F := PB;
   for i:= 0 to n-1 do begin {in parallel, using previous inputs}
       S[i] := (E and F) ⊕ A[i] ⊕ B[i];
       E := (E and (not F)) ⊕ A[i];
       F := ((not E) and F) ⊕ B[i];
   end;
   CE := E; CF := F;
end;

这将灰码单词A和B相加，形成灰码单词S。操作数奇偶校验为PA和PB，和的奇偶校验为PS。它在内部传播两个进位比特E和F，并产生两个外部进位比特CE和CF。

很遗憾，它没有关于减法的说明，但我认为，当您可以编码负数时，可以使用加法来实现。

- Sebastian Dressler

---

哈哈，这是我找到的唯一一篇谈论加法的文档，但我找不到Å代表什么，感谢您的解释 :) 但我仍然有理解上的问题。希望最终能够理解... - Morwenn

@Morwenn 我猜测这个符号的意图是教学性质的，而非实际应用，只是为了演示硬件实现算法。 - Potatoswatter

Answer 2

我接受了@Sebastian Dressler的答案，因为所建议的算法确实可行。为了完整起见，我在此提供一个相应的C99实现（C++兼容）：

// lhs and rhs are encoded as Gray codes
unsigned add_gray(unsigned lhs, unsigned rhs)
{
    // e and f, initialized with the parity of lhs and rhs
    // (0 means even, 1 means odd)
    bool e = __builtin_parity(lhs);
    bool f = __builtin_parity(rhs);

    unsigned res = 0u;
    for (unsigned i = 0u ; i < CHAR_BIT * sizeof(unsigned) ; ++i)
    {
        // Get the ith bit of rhs and  lhs
        bool lhs_i = (lhs >> i) & 1u;
        bool rhs_i = (rhs >> i) & 1u;

        // Copy e and f (see {in parallel} in the original paper)
        bool e_cpy = e;
        bool f_cpy = f;

        // Set the ith bit of res
        unsigned res_i = (e_cpy & f_cpy) ^ lhs_i ^ rhs_i;
        res |= (res_i << i);

        // Update e and f
        e = (e_cpy & (!f_cpy)) ^ lhs_i;
        f = ((!e_cpy) & f_cpy) ^ rhs_i;
    }
    return res;
}

注意: __builtin_parity是一个编译器内置函数（GCC和Clang），返回整数中设置位的数量的奇偶性（如果内置函数不存在，则有其他方法手动计算）。当格雷码具有偶数个设置位时，它是偶数的。该算法仍然可以改进，但这种实现相当忠实于原始算法。如果您想了解优化实现的详细信息，可以查看Code Review上此Q&A。

- Morwenn

Answer 3

我最近设计了一个新的算法来计算两个格雷码之和。不幸的是，它仍然比朴素的双转换解决方案慢，并且也比Harold Lucal的算法（即被接受的答案中的算法）慢。但是，对于问题的任何新解决方案都是受欢迎的，对吧？

// lhs and rhs are encoded as Gray codes
unsigned add_gray(unsigned lhs, unsigned rhs)
{
    // Highest power of 2 in lhs and rhs
    unsigned lhs_base = hyperfloor(lhs);
    unsigned rhs_base = hyperfloor(rhs);

    if (lhs_base == rhs_base) {
        // If lhs and rhs are equal, return lhs * 2
        if (lhs == rhs) {
            return (lhs << 1u) ^ __builtin_parity(lhs);
        }
        // Else return base*2 + (lhs - base) + (rhs - base)
        return (lhs_base << 1u) ^ add_gray(lhs_base ^ lhs, lhs_base ^ rhs);
    }

    // It's easier to operate from the greatest value
    if (lhs_base < rhs_base) {
        swap(&lhs, &rhs);
        swap(&lhs_base, &rhs_base);
    }

    // Compute lhs + rhs
    if (lhs == lhs_base) {
        return lhs ^ rhs;
    }

    // Compute (lhs - base) + rhs
    unsigned tmp = add_gray(lhs ^ lhs_base, rhs);
    if (hyperfloor(tmp) < lhs_base) {
        // Compute base + (lhs - base) + rhs
        return lhs_base ^ tmp;
    }
    // Here, hyperfloor(lhs) == hyperfloor(tmp)
    // Compute hyperfloor(lhs) * 2 + ((lhs - hyperfloor(lhs)) + rhs) - hyperfloor(lhs)
    return (lhs_base << 1u) ^ (lhs_base ^ tmp);
}

该算法需要以下实用函数才能正常工作：

// Swap two values
void swap(unsigned* a, unsigned* b)
{
    unsigned temp = *a;
    *a = *b;
    *b = temp;
}

// Isolate the most significant bit
unsigned isomsb(unsigned x)
{
    for (unsigned i = 1u ; i <= CHAR_BIT * sizeof(unsigned) / 2u ; i <<= 1u) {
        x |= x >> i;
    }
    return x & ~(x >> 1u);
}

// Return the greatest power of 2 not higher than
// x where x and the power of 2 are encoded in Gray
// code
unsigned hyperfloor(unsigned x)
{
    unsigned msb = isomsb(x);
    return msb | (msb >> 1u);
}

---

那么，它是如何工作的？

我必须承认，对于像加法这样“简单”的东西来说，这是一堵相当大的代码墙。它主要基于对格雷码中比特模式的观察；也就是说，我没有正式证明任何东西，但我还没有找到算法不起作用的情况（如果我不考虑溢出，它就无法处理溢出）。以下是构建算法所使用的主要观察结果，假设一切都是格雷码:

• 2 * n = (n << 1) ⊕ 奇偶校验(n)
• 如果a是2的幂次方且a > b，则a ⊕ b = a + b
• 因此，如果a是2的幂次方且a < b，则a ⊕ b = a - b。不过，这仅在b < 2 * a时才有效。
• 如果a和b具有相同的超底并且不相等，则a + b = (超底(a) << 1) ⊕ ((超底(a) ⊕ a) + (超底(b) ⊕ b))。

基本上，这意味着我们知道如何乘以2，如何将一个小的Gray码加上2的幂，以及如何从一个比该幂大但比下一个2的幂小的Gray码中减去一个2的幂。其他所有技巧都是为了让我们能够根据相等的值或2的幂来推理。

如果您想要更多细节/信息，您还可以检查Code Review上这个Q&A，其中提供了现代C++实现算法的一些优化（作为额外奖励，这里有一些漂亮的MathJax方程式：D）。

- Morwenn