用于比较数字的按位运算？

Question

过去一天我在这上面花费了太多的脑力。

我正在尝试提出一组可以重新实现以下条件的按位运算：

uint8_t a, b;
uint8_t c, d;
uint8_t e, f;
...

bool result = (a == 0xff || a == b) && (c == 0xff || c == d) && (e == 0xff || e == f);

我正在查看的代码有四个这样的表达式，短路 && 在一起（如上所述）。

我知道这是一个深奥的问题，但是这个问题的短路性质和上面代码在一个紧密循环中的时间安排使得缺乏可预测的时间成为一种皇家痛苦，坦率地说，这似乎真的吸收分支预测不可用或实施得很好的架构。

有这么会简洁的猛兽吗？

Answer 1

您可以修改存储和解释数据的方式：

当a if 0xFF时，是否需要b的值。如果不是，则使 b 等于 0xFF 并通过删除测试 0xFF.

的部分来简化表达式

此外，您可以将 a、b 和 c 组合在一个变量中。

uint32_t abc;
uint32_t def;

bool result = abc == def;

其他操作可能会更慢，但该循环应该更快（单次比较而不是最多 6 次比较）。

You might want to use an union to be able to access byte individually or in group. In that case, make sure that the forth byte is always 0.

Answer 2

所以，如果您真的想 bit-twiddling 使它变得“快速”（您真的应该只在分析代码以确保这是一个瓶颈之后才这样做），您想要做的是通过将所有值打包成一个更宽的词来对其进行矢量化，这样您就可以一次进行所有比较（一条指令），然后从几位中提取答案。

这有一些技巧。要比较两个值是否相等，您可以对它们进行异或 (^) 并测试结果是否为零。要测试一个更宽的单词的字段以查看它是否为零，您可以 'pack' 它上面有一个 1 位，然后减去一个，看看您添加的额外位是否仍然是 1 -- 如果它现在是 0 ，该字段的值为零。

综上所述，您想同时进行 6 次 8 位比较。您可以将这些值打包到 64 位字的 9 位字段中（9 位以获得额外的 1 个保护位，您将要测试减法）。你最多可以在一个 64 位 int 中容纳 7 个这样的 9 位字段，所以没问题

// pack 6 9-bit values into a word
#define VEC6x9(A,B,C,D,E,F)  (((uint64_t)(A) << 45) | ((uint64_t)(B) << 36) | ((uint64_t)(C) << 27) | ((uint64_t)(D) << 18) | ((uint64_t)(E) << 9) | (uint64_t)(F))

// the two values to compare
uint64_t v1 = VEC6x9(a, a, c, c, e, e);
uint64_t v2 = VEC6x9(b, 0xff, d, 0xff, f, 0xff);
uint64_t guard_bits = VEC6x9(0x100, 0x100, 0x100, 0x100, 0x100, 0x100);
uint64_t ones = VEC6x9(1, 1, 1, 1, 1, 1);
uint64_t alt_guard_bits = VEC6x9(0, 0x100, 0, 0x100, 0, 0x100);

// do the comparisons in parallel
uint64_t res_vec = ((v1 ^ v2) | guard_bits) - ones;

// mask off the bits we'll ignore (optional for clarity, not needed for correctness)
res_vec &= ~guard_bits;

// do the 3 OR ops in parallel
res_vec &= res_vec >> 9;

// get the result
bool result = (res_vec & alt_guard_bits) == 0;

末尾的 OR 和 AND 是 'backwards' 因为如果比较为真（值相等）则每次比较的结果位为 0，如果比较为假（值不相等）则为 1。

如果您正在编写编译器，那么以上所有内容都是您最感兴趣的 -- 它是您最终如何实现向量比较的 -- 很可能矢量化编译器会自动为您完成所有这些工作.

如果您可以安排将初始值 pre-packed 放入向量中，效率会更高。这可能反过来影响您对数据结构和允许值的选择——如果您将您的值安排为 7 位或 15 位（而不是 8 位），当您添加保护位时它们可能会打包得更好......

Answer 3

要删除 &&, || 的时间变化，请使用 &, |。。可能更快，也许不会。肯定更容易并行。

// bool result = (a == 0xff || a == b) && (c == 0xff || c == d) 
//     && (e == 0xff || e == f);
bool result = ((a == 0xff) | (a == b)) & ((c == 0xff) | (c == d))
    & ((e == 0xff) | (e == f));

用于比较数字的按位运算？

Bitwise operations for comparing numbers?

c

c++

bit-manipulation

bitwise-operators