3

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! :-)

larn
  • 398
  • 2
  • 16
  • 2
    Note that this approach only works when your implementation uses two's complement to represent integers (which is admittedly the norm these days). Ref. [Are the results of bitwise operations on signed integers defined?](https://stackoverflow.com/questions/11644362/are-the-results-of-bitwise-operations-on-signed-integers-defined) – Sander De Dycker Feb 24 '20 at 07:38
  • 1
    I think, this cannot be done without using other operations than bit operations (either implicitly or explicitly). A comparison is not a bit-operation (`==`), logical not (`!`) is not a bit operation and constructs like `if (x ^ y)` are also logical operations. The function `ffs()` used below is no c primitive and its implementation also has to use logical operations. – Ctx Feb 24 '20 at 09:42

3 Answers3

4

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.

PooSH
  • 601
  • 4
  • 11
  • Why use the double negation when using the bitwise XOR? The double negation just removes the first negation which makes it completely obsolete. (0 ^ 0 = 0), (0 ^ 1 = 1), (1 ^ 0 = 1), (1 ^ 1 = 0) – Pethead Feb 24 '20 at 07:52
  • 1
    Probably the reason why the OP wants this is some manner of pre-mature optimization. Many architectures will translate `!=` into XOR in the machine code. But the compiler is perfectly capable of doing that optimization. That being said, the function call overhead is what takes time here. – Lundin Feb 24 '20 at 07:53
  • 1
    @Pethead Because XOR is already similar to "not equal", except in case of non-zero results, it can have any value. Whereas `!=` returns exactly `1`, similar to boolean. The double !! turns the non-zero into zero and then turns that into the number `1`. – Lundin Feb 24 '20 at 08:00
  • 2
    @Pethead : `1 ^ 2 == 3`, `!(1 ^ 2) == 0`, `!!(1 ^ 2) == 1` – Sander De Dycker Feb 24 '20 at 08:00
  • @Pethead Usage of `!!` is common practice to map any non-zero value to `true`. – Gerhardh Feb 24 '20 at 08:08
0

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

You could just do the following:

return !(x ^ y);
Pethead
  • 178
  • 2
  • 6
  • 15