CODEWITHSUNDEEP
cbinarybit-manipulation
not_l33t
not_l33t

Reputation: 1345

Replacing "==" with bitwise operators

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

Upvotes: 29

Views: 45486

Answers (6)

Saurabh Sachdeo
Saurabh Sachdeo

Reputation: 41

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

Upvotes: 2

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 798804

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

Upvotes: 84

Eternal Learner
Eternal Learner

Reputation: 3870

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

Upvotes: 0

Fabian Giesen
Fabian Giesen

Reputation: 3311

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.

Upvotes: 20

indiv
indiv

Reputation: 17866

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

Upvotes: 3

sth
sth

Reputation: 229663

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

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

Upvotes: 26

Related Questions