27

Using only bitwise operators (|, &, ~, ^, >>, <<) and other basic operators like +, -, and !, is it possible to replace the "==" below?

int equal(int x, int y) {
    return x == y;
}
5
  • 1
    This is mostly to understand what is actually going on with "==" to see how the computer looks at the "==" on a bitwise level and to find if similar operators can be replicated in the same fashion.
    – not_l33t
    Nov 12, 2010 at 4:41
  • @Jens: "The homework tag...is now discouraged," but, @not_l33t, please (as always) follow general guidelines: state any special restrictions, show what you've tried so far, and ask about what specifically is confusing you.
    – Roger Pate
    Nov 12, 2010 at 14:06
  • What are the requirements as you approach an int's limits? I.e. INT_MAX, INT_MIN? Or does it only have to work for a much smaller range?
    – Roger Pate
    Nov 12, 2010 at 14:09
  • I am fairly new to programming, and the question is more to understand how it works. With that in mind, it would be ideal to have an infinite limit, though I am beginning to see that that might not really be possible for me to figure out (bitwise manipulation works because of the 32 bit string).
    – not_l33t
    Nov 12, 2010 at 15:55
  • I'd like to mention for anyone trying to use bitwise operations as a performance boost that at least in chrome 61 there is little to no difference between regular equals and bitwise equals methods. jsperf.com/bitwise-equal/1 Oct 4, 2017 at 3:27

6 Answers 6

82

Remember that an XOR is the exactly same as NOT EQUALS and XNOR is exactly the same as EQUALS. So, the following will give you exactly what you want:

return !(x ^ y);
4
  • 2
    You're combining bit-wise with logical operators here, which may be confusing. Nov 12, 2010 at 4:46
  • 12
    It's better than the accepted solution, because by definition XOR is faster than ADD (add have to transport carry, so it's not very scalable).
    – ruslik
    Nov 12, 2010 at 9:44
  • what if x and y both are zeroes May 29, 2017 at 16:53
  • 1
    @Kapil: Huh? 0 XOR 0 equals 0, just as if x and y were any other same number. May 29, 2017 at 17:10
26

Two numbers are equal if there is no difference between them:

int equal(int x, int y){
   return !(x-y);
}
5
  • 6
    Though not really using a bitwise operator.
    – Yada
    Nov 12, 2010 at 4:44
  • @Yada: But it uses a "BASIC" operator :)
    – AbdullahC
    Nov 12, 2010 at 4:47
  • I have used this approach in combination with another approach (negating a variable). that way i could use a + instead, making it closer to what the computer reads. thus making it faster?
    – not_l33t
    Nov 12, 2010 at 5:30
  • int equal(int x, int y){ return !((!x+1)+y); }
    – not_l33t
    Nov 12, 2010 at 5:31
  • 4
    this may invoke undefined behavior if the result of x-y cannot be represented in int
    – phuclv
    Jan 26, 2015 at 4:35
20

The C ! operator is really just shorthand for != 0, so using it seems very close to cheating :)

Here's my take just using bitwise operations, assuming a 32-bit two's complement machine with arithmetic right shifts (technically, in C arithmetic right shifts are undefined, but every C compiler I've ever seen on a two's complement machine supports this correctly):

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

That said, actual compilers don't have this problem. Real hardware actually has direct support for comparisons. The details depend on the architecture, but there's two basic models:

  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.

2
  • excellent example! but why just not use "return t < 0 ? false : true" (if assume the method is boolean)? Jun 3, 2014 at 14:15
  • 1
    As I understand it, the OP excludes branching
    – edgerunner
    Mar 13, 2017 at 10:51
3

This example is the same as subtraction, but is more explicit as to how some architectures do register comparison (like the ARM, I believe).

return !(1 + ~x + y);

The 1 signifies the carry-bit input into the ALU. One number x is bitwise complemented. Taking the complement and adding 1 produces the two's complement of the number (x becomes -x), and then it's added to the other number to get the difference to determine equality.

So if both numbers are equal, you get -x + x => 0.

(On a register level the ! operator isn't done, and you just test the "zero bit" of the condition codes or flags register, which gets set if the register operation produces a result of zero, and is clear otherwise.)

2

As XOR is same as (!=), hence (x ^ y) will return 0 only for equal values. My take is the following because it is sensible, uses bit-wise operator and working.

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

My Take on this

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

Explanation: If x == y, then x & ~y evaluates to 0 return 1, else return 0 as x!=y.

Edit1: The above is equivalent to 

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

The above code fails in certain cases where the Most significant bit turns to 1. The solution is to add a 1. i.e correct answer is

return !(x & (~y +1) );
3
  • Two problems. 1) This checks if y has all the same bits as x set, not that x == y. 2) You're using == even though it is neither wanted nor needed. Nov 12, 2010 at 7:09
  • 3
    3) just return it instead of using an if.
    – mpen
    Nov 12, 2010 at 7:38
  • I know is old, but what happens if x is negative? Lets say x = -1 and y = 0 then how should if ( !( x & ( ~( y + 1 )) ) ) Work ? How about if x = -1 and y = -1? ´return x ^ y:` should work.
    – Michi
    Jan 7, 2019 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.