快速比较位运算

Question

我有两个字节，每个字节由两个4位数字组成。我需要知道第一个字节中的任意一个数字是否与第二个字节中的任意一个数字匹配。零被视为null，不应与自己匹配。

显然，我可以通过逐一解包数字并进行比较来实现这一点：

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

不过我在想，是否有更简洁的方法来实现这个功能？

- Niet the Dark Absol

Answer 1

预先计算答案并将其存储在查找表中。您的表的关键是16位((a<<8)+b)。它只需要1位输出（使用8K），但为了简单起见，您可以使用8位（使用64K）。

- Keith Randall

---

一般来说，预计算是一个好主意，但这个调用只会在脚本的生命周期中执行一次。即使我手动进行预计算并将原始结果放入数组中，创建该数组可能会比计算所需的单个结果更昂贵。 - Niet the Dark Absol

你也可以使用一个256x16位的表格，然后提取2位：((table[a]>>(b&15)) | (table[a]>>(b>>4))) & 1。表格也非常容易计算：对于0到255中的x，table[x] = ((1<<(x&15)) | (1<<(x>>4))) & 0xfffe。 - Chris Dodd

如果您只需要偶尔执行此操作，那么使用表格查找是得不偿失的。那问题究竟在哪里呢？ - Keith Randall

预计算是一种时空权衡...但如果查找表不适合数据缓存（或者使用稀疏或不频繁），当您进行查找时，可能会出现缓存未命中的情况，并且访问DRAM可能会花费您200个处理器周期 - 当您在缓存中命中时，可以完成很多处理工作。 - amdn

Answer 2

更好的方法是摆脱那个难以解析的表达式，使代码更易读。

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

任何优秀的优化编译器基本上都会给出相同的底层代码，所以有时更好的优化方式是为可读性而优化。

- paxdiablo

---

这不是和我的代码完全一样，只是多了些空格吗？除了额外的检查以确保ah和bh确实是4位长（在我的情况下是不必要的，因为它们来自MySQL的TINYINT UNSIGNED字段，但我没有提到），我没有看到任何功能上的区别。当我说“更清晰”时，我更多地是指机器可解析性。 - Niet the Dark Absol

是的，它是等效的。我的观点是，您可能不需要担心机器可解析性。机器足以处理您的原始代码。您需要关注的是其他人（或六个月后的自己）对您的代码的可解析性。 - paxdiablo

这就是注释的作用:D - Niet the Dark Absol

@Kolink 当你说“机器可解析性”时，你真的是在指机器的性能吗？ - Michael McGowan

Answer 3

这里有一个更简洁且快1.6倍的C++解决方案。它生成的代码更适合具有深度流水线和复杂分支预测逻辑的高端微处理器。它生成的true/false没有比较/分支和表查找（没有数据缓存未命中）。

一个nibble有4位，因此可以保存16个值，我将每个输入中的两个nibbles映射到一个无符号值（至少有16位），并在相应的位位置设置位，表示输入中存在两个nibble值。然后我使用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
$ 

- amdn