5

2 つの 4 ビット数値をまとめて構成された 2 バイトがあります。最初のバイトの 2 つの数値のいずれかが、2 番目のバイトの数値のいずれかと一致するかどうかを知る必要があります。ゼロは null と見なされ、それ自体と一致してはなりません。

明らかに、数値を展開して 1 つずつ比較することでこれを行うことができます。

a = 0b10100101;
b = 0b01011111; // should have a match because 0101 is in both

a1 = a>>4; a2 = a&15;
b1 = b>>4; b2 = b&15;

return (a1 != 0 && (a1 == b1 || a1 == b2)) || (a2 != 0 && (a2 == b1 || a2 == b2));

//     ( true   && (  false  ||   false )) || ( true   && (  true   ||   false ))
//     ( true   &&         false         ) || ( true   &&         true          )
//            false                        ||         true
//                                        TRUE

しかし、これを行うためのよりクリーンな方法を誰かが知っているかどうか疑問に思っていますか?

4

3 に答える 3

2

答えを事前に計算し、ルックアップ テーブルに格納します。テーブルのキーは 16 ビット((a<<8)+b)です。必要なのは 1 ビット出力 (8K を使用) だけですが、簡単にするために 8 ビットを使用することもできます (64K を使用)。

于 2012-08-28T02:46:50.213 に答える
0

よりクリーンな方法は、解析が難しい式を取り除き、コードを読みやすくすることです。

def sameNybble (a, b):
    # Get high and low nybbles.

    ahi = (a >> 4) & 15 ; alo = a & 15;
    bhi = (b >> 4) & 15 ; blo = b & 15;

    # Only check ahi if non-zero, then check against bhi/blo

    if ahi != 0:
        if ahi == bhi or ahi == blo:
            return true

    # Only check alo if non-zero, then check against bhi/blo

    if alo != 0:
        if alo == bhi or alo == blo:
            return true

    # No match

    return false

適切な最適化コンパイラは基本的に同じ基礎となるコードを提供するので、読みやすさのために最適化する方が良い場合があります。

于 2012-08-28T02:44:47.433 に答える
0

これは、より簡潔で 1.6 倍高速な C++ のソリューションです。深いパイプラインと複雑な分岐予測ロジックを備えたハイエンド マイクロプロセッサに適したコードを生成します。比較/分岐なし、テーブル ルックアップなし (データ キャッシュ ミスなし) で true/false を生成します。

ニブルには 4 ビットがあり、したがって 16 の値の 1 つを保持します。各入力の 2 つのニブルを符号なし値 (少なくとも 16 ビットを持つ) にマップし、対応するビット位置に設定されたビットを使用して、入力。次にAND、2 つのビットセットを計算して、セットの共通部分を計算します。最後ANDは nibble との一致を破棄します0。

inline unsigned set( unsigned char X ) {
    return (1 << (X & 15)) | (1 << (X >> 4));
}

// Return true if a nibble in 'A' matches a non-null nibble in 'B'
inline bool match( unsigned char A, unsigned char B ) {
    return set( A ) & set( B ) & ~set( 0 );
}

Intel Xeon X5570 @ 2.93GHz で計測したところ、質問のオリジナルよりも 1.6 倍高速です。時間を計るのに使用したコードは次のとおりです。

#include <time.h>
#include <iostream>

bool original( unsigned char A, unsigned char B ) {
    unsigned char a1 = A >> 4;
    unsigned char a2 = A & 15;
    unsigned char b1 = B >> 4;
    unsigned char b2 = B & 15;

    return (a1 != 0 && (a1 == b1 || a1 == b2)) || (a2 != 0 && (a2 == b1 || a2 == b2));
}

static inline unsigned set( unsigned char X ) {
    return (1 << (X & 15)) | (1 << ((X >> 4)&15));
}

bool faster( unsigned char A, unsigned char B ) {
    return set( A ) & set( B ) & ~set( 0 );
}

class Timer {
    size_t _time;
    size_t & _elapsed;
    size_t nsec() {
        timespec ts;
        clock_gettime( CLOCK_REALTIME, &ts );
        return ts.tv_sec * 1000 * 1000 * 1000 + ts.tv_nsec;
    }
public:
    Timer(size_t & elapsed) : _time(nsec()), _elapsed(elapsed) {}
    ~Timer() { _elapsed = nsec() - _time; }
};

int main()
{
    size_t original_nsec, faster_nsec;
    const size_t iterations = 200000000ULL;
    size_t count = 0;

    { Timer t(original_nsec);
        for(size_t i=0; i < iterations; ++i) {
            count += original( 0xA5 , i & 0xFF );
        }
    }

    { Timer t(faster_nsec);
        for(size_t i=0; i < iterations; ++i) {
            count += faster( 0xA5 , i & 0xFF );
        }
    }

    std::cout << double(original_nsec) / double(faster_nsec)
              << "x faster" << std::endl;

    return count > 0 ? 0 : 1;
}

出力は次のとおりです。

$ g++ -o match -O3 match.cpp -lrt && ./match
1.61564x faster
$
于 2012-08-28T13:37:15.797 に答える