CODEWITHSUNDEEP
cbitwise-operators
larn
larn

Reputation: 398

Not equal using bitwise operations?

I'll be forthright about this: this one is for homework. However, as I've already completed the question and was just simply curious about different implementations of what I did, I thought it was okay to be consult y'all.

The question was to build a != function using bitwise operations. We are also allowed to use ! and +.

Returns 0 if x==y, otherwise it returns 1. 

int eval_not_equal(int x, int y) {
    int result = x ^ y;
    if(result == 0) {
        result = 0;
    }
    else {
       result = 1; 
     }
    return result;
}

I think this is a perfectly fine answer to the question, but I was wondering if it's possible to do this without using an if? There are quite a few different bitwise operations, and I'm sure there's gotta be a way to use them in order to replace the if that I used!

Would love to know what you guys think! :-)

Upvotes: 3

Views: 2173

Answers (3)

user21192786
user21192786

Reputation:

You could use double negation and a series of XOR's to accomplish this like this. This also works for negative numbers.

  • i32 is just a 32bit signed int
inline i32 negate(i32 x){ return ((x >> 31) | ((~x + 1) >> 31)) + 1; }
inline i32 ne(i32 a, i32 b){ return negate(a ^ b) ^ 1; }

int main(){
    printf("result=%i\n", ne(-1, -1)); // 0
    printf("result=%i\n", ne(-5, 0));  // 1
    printf("result=%i\n", ne(0, 0));   // 0
    printf("result=%i\n", ne(5, 5));   // 0
    printf("result=%i\n", ne(1, 5));   // 1
    printf("result=%i\n", ne(5, 1));   // 1
    return 0;
}

Upvotes: 0

PooSH
PooSH

Reputation: 701

I do not understand why you cannot use operator !=:

int eval_not_equal(int x, int y) {
    return x != y;
}

but if that is some kind of challenge to avoid != in the code, then you can write like this:

int eval_not_equal(int x, int y) {
    return !!(x ^ y);
}

In the code above, the result of x ^ y is treated as bool, then negated. The boolean equivalent of "false" is 0; "true" by default is 1 (but actually any non-zero integer is true)

If this is C++, or usage of stdbool is permitted (C99), then you can do also like this:

int eval_not_equal(int x, int y) {
    return (bool) (x ^ y);
}

Update:

The question was to build a != function using only bitwise operations

If "only" is the key, then neither mine previous answers nor OP's solution are valid because ! is a boolean operator not bitwise. The same applies to type cast (bool) or if clause.

In my honest opinion, the following code is ridiculous, but it uses only bitwise operations:

int eval_not_equal(int x, int y) {
    int xo = (x ^ y);
    return (xo >> (ffs(xo) - 1)) & 1;
}

Function ffs() returns first set bit, i.e. the index of the first bit which equals to 1. We want only that bit, so we shift right the xor result by ffs - 1 to get rid of all lower bits, then do bitwise-and-with-1 to clear higher bits.

Upvotes: 4

Pethead
Pethead

Reputation: 178

You could just do the following:

return !(x ^ y);

Upvotes: -1

Related Questions