c - 如何编写将 0xFF 置于匹配通道中的 SWAR 比较？

Question

我正在尝试编写一个 SWAR 比较相等操作，uint64_t假装是uint8_t. 根据 Hacker's Delight 和 Bit Twiddling Hacks 中的技术，我设法达到的最接近的结果如下：

uint64_t compare_eq (uint64_t x, uint64_t y) {
    uint64_t xored = x ^ y;
    uint64_t mask = 0x7F * 0x0101010101010101ULL;
    uint64_t tmp = (xored & mask) + mask;
    return ~(tmp | xored | mask);
}

但是，这会放入0x80匹配的0x00“车道”和不匹配的“车道”，而我想要匹配的“车道”和不0xFF匹配0x00的“车道”。是否可以在没有分支的情况下编写它？

Answer 1

作为记录，这只是计算非零字节中的高位（少一条指令）与@njuffa 和@Nate Eldredge 的评论（可能比4386427 的答案更有效）的一种变体。

uint64_t compare_eq (uint64_t x, uint64_t y) {
    uint64_t xored = x ^ y;
    uint64_t mask = ((((xored >> 1) | 0x8080808080808080) - xored) & 0x8080808080808080);
    return (mask << 1) - (mask >> 7);
}

Answer 2

首先，发布的代码中有一个错误（错字？）：

uint64_t mask = 0x7F * 0x0101010101010101ULL;
                       ^^
                    Missing 0x

一旦通道中有 0x80 或 0x00，您可以除以 0x80 并乘以 0xff。

喜欢：

uint64_t compare_eq (uint64_t x, uint64_t y) {
    uint64_t xored = x ^ y;
    uint64_t mask = 0x7F * 0x0101010101010101ULL;
    uint64_t tmp = (xored & mask) + mask;
    uint64_t res = ~(tmp | xored | mask);
    res = res / 0x80;
    res = res * 0xff;
    return res;
}