格雷码添加

Question

有没有任何已知的方法来计算两个格雷码的加法(也许是减法),而不必将两个格雷码转换为常规二进制,执行二进制加法然后将结果转换回格雷码？我设法编写递增和递减函数,但加法和减法似乎记录更少,更难写.

Answer 1

在本文档之下#6,有用于串行格雷码添加算法(直接复制;请注意,这?是xor):

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.

不幸的是,它没有说明有关减法的任何内容,但我认为,当你可以编码负数时,你可以使用加法.

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),它返回整数中设置位数的奇偶校验(如果内部函数不存在,则还有其他方法可以手动计算它).灰度代码即使具有偶数个设置位也是如此.该算法仍然可以改进,但这种实现相当忠实于原始算法.如果您需要有关优化实施的详细信息,可以查看有关代码审查的此问答.