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

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);