测试固定集是否相等且无分支

Question

我有一组整数 (x, y, z) 和一个采用 3 个整数 (u, v, w) 的函数。如何测试 (x,y,z) == (u,v,w) ？天真的方法是：

bool match = (x == u || x == v || x == w) && (y == u || y == v || y == w) && (z == u || z == v || z == w);

有人知道一些智能位运算/算术可以做同样的事情吗？

我可以假设 (x, y, z) 或 (u, v, w) 都不包含重复项。

Answer 1

在这种情况下，您可以用按位运算替换逻辑运算以消除分支：

bool match = (x == u | x == v | x == w)
           & (y == u | y == v | y == w)
           & (z == u | z == v | z == w);

但是，您必须测量性能影响以确定这是更快还是更慢。

Answer 2

您可以通过在进行实际测试之前转换为无符号并比较总和来预先消除一堆不相等的向量。

Answer 3

如果 a 和 b 相同，则 a^b 为零。因此，仅当 a 和 b 相同时 !(a^b) 才非零。假设您的平台可以在没有分支的情况下执行逻辑“not”，因此您可以使用单个分支测试 a 是否是 (u, v, w) 的成员：

if(!(a^u) | !(a^v) | !(a^w))

因此是否所有 (x, y, z) 都是成员(u, v, w) 的使用：

if(
    (!(a^u) | !(a^v) | !(a^w))) &
    (!(b^u) | !(b^v) | !(b^w))) &
    (!(c^u) | !(c^v) | !(c^w))))

即仅对各种结果执行按位与操作，并且再次仅执行单个分支。

如果您的平台需要一个分支来执行 !，例如，如果它本质上是作为 a 执行的？ 0 : -1，那么这就是十个条件，并不比简单的解决方案更好。

Answer 4

在 C 语言中，没有分支就无法做到这一点。

如果您愿意内联汇编，可以使用一些 CMPXCHG 指令来完成此操作。

Answer 5

正如评论中所指出的，只要 (x,y,z) 中的所有元素都包含在集合 (u,v,w) 中，你的“天真的”方式就会匹配。如果您确实想测试这些集合是否相等，您可能需要

 (x==u && ((y==v && z==w) || (y==w && z==v))) ||
 (y==u && ((z==v && x==w) || (x==w && z==v))) ||
 (z==u && ((x==v && y==w) || (y==w && x==v)));

您可以快速过滤掉许多不匹配的情况，

  bad = (x+y+z) - (u+v+w);

某些处理器具有非分支“最小”和“最大”指令，这将允许您执行以下操作：

  a = min(x,y)
  b = max(x,y)
  c = min(b,z)
  x = min(a,c)
  y = max(a,c)
  z = max(b,z) 
  //repeat sorting sequence for u,v,w
  match = (x==u)&(y==v)&(z==w);