5

我有两个字节，它们由两个 4 位数字打包在一起组成。我需要知道第一个字节中的两个数字中的任何一个是否与第二个字节中的任何一个数字匹配。零被认为是空的，不应该匹配自己。

显然，我可以通过拆开数字并一一比较来做到这一点：

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

这是 C++ 中的一个解决方案，它更简洁，速度提高了 1.6 倍。它生成的代码对具有深管道和复杂分支预测逻辑的高端微处理器更友好。它生成真/假，没有比较/分支，也没有表查找（没有数据缓存未命中）。

一个半字节有 4 位，因此保存 16 个值之一，我将每个输入中的两个半字节映射到一个无符号值（至少有 16 位），位设置在相应的位位置，指示两个半字节值都存在于输入。然后我AND两个位集，从而计算集合的交集。最后一个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 回答