17

2 つのグレイ コードを通常のバイナリに変換せずに 2 つのグレイ コードの加算 (およびおそらく減算) を計算し、バイナリ加算を実行してから結果をグレイ コードに戻す既知の方法はありますか? インクリメント関数とデクリメント関数を書くことはできましたが、加算と減算はさらに文書化されておらず、書くのが難しいようです。

4

3 に答える 3

11
于 2014-01-04T19:57:01.777 に答える
6

提案されたアルゴリズムが実際に機能するため、@ 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) です (組み込みが存在しない場合は、手動で計算する他の方法があります)。偶数のビットが設定されている場合、グレイ コードは偶数です。アルゴリズムはまだ改善される可能性がありますが、この実装は元のアルゴリズムにかなり忠実です。最適化された実装について詳しく知りたい場合は、コード レビューに関するこの Q&Aをご覧ください。

于 2014-11-06T13:54:05.697 に答える
3

私は最近、2 つのグレイ コードを追加する新しいアルゴリズムを考案しました。残念ながら、単純な二重変換ソリューションよりも遅く、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
  • したがって、ia は 2 のべき乗であり、a < b の場合、a ⊕ b = a - b となります。ただし、これは b < 2 * a の場合にのみ機能します。
  • a と b が同じハイパーフロアを持つが等しくない場合、a + b = (hyperfloor(a) << 1) ⊕ ((hyperfloor(a) ⊕ a) + (hyperfloor(b) ⊕ b)) となります。

基本的には、2 を掛ける方法、2 のべき乗を小さいグレイ コードに加算する方法、2 のべき乗より大きいが次の値より小さいグレイ コードから 2 のべき乗を引く方法を知っていることを意味します。等値または 2 のべき乗で推論できるように、他のすべてはトリックです。

詳細/情報が必要な場合は、アルゴリズムの最新の C++ 実装といくつかの最適化を提案しているコード レビューのこの Q&Aを確認することもできます (おまけとして、ここでは使用できない優れた MathJax 方程式がいくつかあります。 D）。

于 2015-04-08T08:09:03.130 に答える