使用位运算符代替"=="

Question

只使用按位运算符（|，&，~，^，>>，<<）和其他基本运算符（如+，-和!），是否可以替换下面的“==”？

int equal(int x, int y) {
    return x == y;
}

- not_l33t

---

这主要是为了理解 "==" 实际上是怎样运作的，以了解计算机如何在位级别上看待 "=="，并找出是否可以以同样的方式复制类似的运算符。 - not_l33t

@Jens: "The homework tag...is now discouraged," 但是，@not_l33t，请（像往常一样）遵循通用指南：说明任何特殊限制，展示你已经尝试过的内容，并询问具体什么让你感到困惑。 - Roger Pate

当你接近int的极限时，有哪些要求？例如INT_MAX、INT_MIN？或者它只需要适用于更小的范围？ - Roger Pate

我对编程还比较新，这个问题更多是为了理解它的工作原理。考虑到这一点，拥有一个无限制的限制将是理想的，尽管我开始意识到这对我来说可能真的不可能弄清楚（位操作之所以有效是因为32位字符串）。 - not_l33t

我想提醒任何试图使用位运算作为性能提升的人，在Chrome 61中，常规等于和位等于方法之间几乎没有区别。https://jsperf.com/bitwise-equal/1 - FelisPhasma

Answer 1

要记住，XOR与NOT EQUALS完全相同，XNOR与EQUALS完全相同。因此，以下代码将给您提供所需的准确结果:

return !(x ^ y);

- Ignacio Vazquez-Abrams

---

你在这里将按位运算符与逻辑运算符结合使用，可能会令人困惑。 - David Titarenco

XOR 的速度比 ADD 更快（因为 ADD 需要传递进位，所以不太可扩展），因此它比已接受的解决方案更好。 - ruslik

如果x和y都是零怎么办？ - PapaDiHatti

@Kapil：什么？0 XOR 0等于0，就像x和y是任何其他相同的数字一样。 - Ignacio Vazquez-Abrams

Answer 2

如果两个数之间没有差异，那么它们是相等的：

int equal(int x, int y){
   return !(x-y);
}

- sth

---

虽然没有真正使用位运算符。 - Yada

@Yada：但它使用了“BASIC”运算符 :) - AbdullahC

我在这个方法中结合了另一种方法（否定一个变量）。这样我可以使用一个加号，使其更接近计算机的读取方式。从而使其更快速？ - not_l33t

int equal(int x, int y){ return !((!x+1)+y); }相等的整数（int equal）{ 返回！（（！x + 1）+ y）; } - not_l33t

如果 x-y 的结果无法用 int 表示，这可能会导致未定义的行为。 - phuclv

Answer 3

C ! 操作符实际上只是 != 0 的简写，因此使用它似乎非常接近作弊 :)

以下是我的方法，只使用位运算，假设使用32位二进制补码机器和算术右移（严格来说，在C中算术右移是未定义的，但我见过的每个C编译器都在二进制补码机器上正确支持这个）：

int t = (x - y) | (y - x); // <0 iff x != y, 0 otherwise
t >>= 31; // -1 iff x != y, 0 otherwise
return 1 + t; // 0 iff x != y, 1 otherwise

话虽如此，实际编译器并没有这个问题。真正的硬件实际上直接支持比较。细节取决于体系结构，但基本有两种模型：

1. Condition codes returned for arithmetic operations (e.g. x86 and ARM do this). In this case, there's usually a "compare" instruction which subtracts two values, doesn't write back to an integer register but sets the condition code/flags based on the result.

2. More RISC-like platforms typically have direct "branch if equal" and "branch if less than" operands that do a comparison and branch based on the result. It's basically equivalent to the C code

   if (a == b) goto label;
   

   or

   if (a < b) goto label;
   

   all in one machine instruction.

- Fabian Giesen

---

很好的例子！但为什么不直接使用“return t < 0 ? false : true”（如果假设该方法是布尔类型）呢？ - Vladimir Kishlaly

据我理解，OP排除了分支。 - edgerunner

Answer 4

这个例子与减法相同，但更明确地说明了一些架构如何进行寄存器比较（例如ARM）。

return !(1 + ~x + y);

1表示进位位输入到ALU。一个数x按位取反。将补码加1并求反产生该数的二进制补码（x变为-x），然后加到另一个数上以得到差异来确定相等性。因此，如果两个数字相等，你会得到-x + x => 0。在寄存器级别上，不执行！运算符，只需测试条件代码或标志寄存器的“零位”，如果寄存器操作产生零的结果，则设置它，否则清除它。

- indiv

Answer 5

由于异或运算（XOR）等同于不等于（!=），因此仅当两个值相等时，(x ^ y) 才会返回0。 我的看法是以下这样，因为它是合理的，使用了位运算符并且可行。

int notEqual(int x, int y){
        return (x ^ y);
}

- Saurabh Sachdeo

Answer 6

我的看法是

int equal(int x, int y){
   if((x & ~y) == 0)
       return 1;
   else
       return 0; 
}

解释：如果 x == y，那么 x & ~y 的值为 0，返回 1；否则返回 0，因为 x!=y。

Edit1: The above is equivalent to 

int equal(int x, int y){
    return !(x & ~y) ; // returns 1 if equal , 0 otherwise. 
}

上述代码在某些情况下会失败，其中最高有效位变为1。解决方案是添加一个1。即正确答案为

return !(x & (~y +1) );

- Eternal Learner

---

两个问题。1）这个检查是否“y”与“x”设置了完全相同的位，而不是“x == y”。2）即使不需要也不想要，但你还在使用“==”。 - Ignacio Vazquez-Abrams

用 return 代替 if 来返回结果。 - mpen

我知道这是老问题，但如果 x 是负数会发生什么？假设 x = -1 且 y = 0，那么 if ( !( x & ( ~( y + 1 )) ) ) 应该如何工作？如果 x = -1 且 y = -1 呢？return x ^ y: 应该可以解决。 - Michi