我们有两对数字。第一对由 组成，a1, a2第二对由 组成b1, b2。我们希望确定 的任何元素a是否在 中b，反之亦然。这很简单：
int a1, a2, b1, b2;
// is it possible to do better than this:
boolean hasOverlap = a1 == b1 || a1 == b2 || a2 == b1 || a2 == b2;
问题是，理论上是否可以更快地做到这一点？也许通过巧妙地使用按位算术？
为清晰而编辑：为了明确起见，假设我们正在尝试优化一个 java 程序。
假设我们有任意数量的对，而不是只有两对。您可以想象一个由 100 个长度为 2 的数组组成的数组。如果该对包含出现在列表中另一对中的元素，那么从该列表中删除任何对最有效的是什么？
例如：[[1,2], [3,4], [2,5]]将减少为[[3,4]]
从算法的角度来看，第一个问题是无意义的，因为每个解决方案都将具有相同的复杂度（即 O(1)）。
对于奖金问题，这相当于在列表中查找重复项的问题（如果一个数字出现两次，只需检查它是否出现在不同的对中）并且可以通过排序在 O(n*Log(n)) 中完成列表，然后使用先前看到的数字的哈希集扫描它以查找等于或在 O(n) 中的连续数字。
有关按位运算在 Java 中比逻辑运算更快的原因，请参阅以下答案：https ://stackoverflow.com/a/11052460/758446
因此，让我们将原始逻辑运算转换为按位运算：
boolean hasOverlap = a1 == b1 || a1 == b2 || a2 == b1 || a2 == b2;
boolean hasOverlap = !(a1 ^ b1) | !(a1 ^ b2) | !(a2 ^ b1) | !(a2 ^ b2);
请注意，这是混合 C 和 Java 风格的按位操作，不会完全在 Java 中编译。如果有人有制作此编译的提示，请发表评论。自从我在 Java 中进行位操作以来已经有一段时间了。
与@BlackVegetable 的工作方式类似，但执行与 0 的显式比较，因为 java 不会为我们进行转换：
boolean hasOverlap = ((a1 ^ b1) == 0) | ((a1 ^ b2) == 0) | ((a2 ^ b1) == 0) | ((a2 ^ b2) == 0);
|在这里，我认为只有在你有充分理由使用它的情况下才使用按位或应该使用它。与以下情况相比，您错过了短路，这似乎很可能对性能产生比任何其他收益更大的影响：
boolean hasOverlap = ((a1 ^ b1) == 0) || ((a1 ^ b2) == 0) || ((a2 ^ b1) == 0) || ((a2 ^ b2) == 0);
由于通常与 0 相比效率更高，因此那里可能会提高效率。不过，我对此表示严重怀疑，因为我确信设计 JVM 的人会发现他们可以实现int == int为int ^ int == 0.
这个对我来说似乎更有趣：
boolean hasOverlapmul = ((a1 ^ b1) * (a1 ^ b2) * (a2 ^ b1) * (a2 ^ b2))==0;