CODEWITHSUNDEEP
javabit-manipulationsignzero
Michael Choi
Michael Choi

Reputation: 630

Fastest Two Number Sign Comparison Including Zero

What is the fastest way to find if two numbers have the same sign considering that the sign can either be positive, negative or zero.

Commonly, you can say two numbers have same signs with this:

Math.signum(int1) == Math.signum(int2);

You can optimize this by using this:

int1 ^ int2 >= 0;

however, this is making the assumption that zero is positive. What are some ways that will return true including zero.

Some examples of errors would be:

a = 0; b = 1;
boolean test = a ^ b >= 0

where test would yield true instead of false.

I ran some testbenchs and found that the bitwise function returns values faster by nearly 4 orders of magnitude. Since this is a function I will be using in a very large tree for every node, I need to optimize this as much as possible.

I would post an attempted solution, but I can't find one that beats the original one.

Edit: I realize there is a similar problem found here: Fastest way to check if two integers are on the same side of 0 I am asking if there is a way to find if signs are the same INCLUDING zero. so comparisons between 1 and 1 is true, -1 and -1 is true, 0 and 0 is true, 0 and 1 is false, 0 and -1 is false, etc. This is not the same thing as the question asked above!

Upvotes: 2

Views: 495

Answers (3)

Matthew McPeak
Matthew McPeak

Reputation: 17944

Here's what I came up with:

private static boolean signcmp(int x, int y) {
    return ((( x >> 31) | (-x >>> 31)) ^ (( y >> 31) | (-y >>> 31))) == 0; 
}

Upvotes: 2

Dawood ibn Kareem
Dawood ibn Kareem

Reputation: 79876

Without having benchmarked this, I doubt whether you could do any better than

sameSign = a < 0 ? b < 0 : ( a == 0 ) == ( b == 0 );

Upvotes: 0

user555045
user555045

Reputation: 64913

You could use an integer version of signum, such as (not tested):

int signum(int x) {
    int m = x >> 31;
    int neg_m = -x >> 31;
    return m - neg_m;
}

Here m will be -1 iff x < 0 (0 otherwise), and neg_m will be -1 iff x > 0 (ignoring Integer.MIN_VALUE). Their difference is,

  • -1, for x < 0
  • 0, for x == 0
  • 1, for x > 0

It also gives 0 for Integer.MIN_VALUE, but since that never occurs in your case that shouldn't matter.

Upvotes: 1

Related Questions