CODEWITHSUNDEEP
javaoperators
dtech
dtech

Reputation: 14060

Implement relational operator with arithmetic/bitwise operators

Assuming:

Can you implement relational operators like < and == using only arithmetic and bitwise operators?

Upvotes: 1

Views: 213

Answers (2)

doynax
doynax

Reputation: 4455

Here's a quick attempt. Signed less-than is messy but possible in 32-bit arithmetic if needed.

int32_t cmp_lt(int32_t lhs, int32_t rhs) {
    int64_t tmp = lhs;
    tmp -= rhs;
    tmp >>= 63;
    return tmp & 1;
}

int32_t cmp_eq(int32_t lhs, int32_t rhs) {
    return (cmp_lt(lhs, rhs) | cmp_lt(rhs, lhs)) ^ 1;
}

// 32-bit only version
int32_t cmp_lt32(int32_t lhs, int32_t rhs) {
    int32_t tmp = lhs - rhs;
    // -lhs < +rhs is always true
    tmp |= ~rhs & lhs;
    // +lhs < -rhs is always false
    tmp &= ~rhs | lhs;
    tmp >>= 31;
    return tmp & 1;
}

edit: I see that Java was asked for. Not my native language but I believe the regular integer and long types could be substituted for int32_t and int64_t here.

Upvotes: 1

Slicedpan
Slicedpan

Reputation: 5015

I think the less than/greater than can be implemented by subtracting one from the other, casting to an unsigned int and then use a bitwise AND with the sign bit, then shift it to the least significant bit.

Equality could be done with a binary NOT on the result of subtracting the two numbers. Haven't tested these, but used something similar in OpenCL years ago to prevent branching on the GPU.

Example for greater than:

#include <stdio.h>

int main(int argc, char** argv) {
  int x = 6;
  int y = 4;
  int diff;
  unsigned int* udiff;
  unsigned int gr;
  unsigned int one = 1;

  diff = x - y;
  udiff = (unsigned int*)&diff;
  gr = (*udiff & (one << 31)) >> 31;

  printf("%d", gr);


}

(codepad)

Less than can be done analogously. Equality:

#include <stdio.h>

int main(int argc, char** argv) {
  int x = 4;
  int y = 4;

  int diff;
  unsigned int* udiff;
  unsigned int eq;

  diff = x - y;
  udiff = (unsigned int*)&diff;

  eq = !(*udiff);

  printf("%d", eq);

}

(codepad)

Not sure how you can do this in Java, this relies on the fact that you can reinterpret a signed integral value as an unsigned int in C using pointer casting.

Upvotes: 0

Related Questions