CODEWITHSUNDEEP
javaperformancexor
durron597
durron597

Reputation: 32343

Fastest way to check if two integers are on the same side of 0

I need to check if two integers are on the same side of zero many times. I don't care if it's positive or negative, just that it's the same side... and performance is very important.

Currently I'm doing this:

if (int1 == 0 || int2 == 0) {
    // handle zero
} else if ((int1 ^ int2) > 0) {
    // different side
} else {
    // same side
}

This is a 30% improvement in speed (tested with caliper) over the more obvious:

if ((int1 > 0 && int2 > 0) || (int1 < 0 && int2 < 0)) {

Can it be done faster?

If anyone wants to see the test framework I'm using for the 30%, it's here. I used caliper 0.5-rc1

NOTE: All of these solutions check the first bit, basically, which for zero is the same as a positive number. So if that works for your application, you don't need to do a zero check.

Benchmark list:

Caliper output:

0% Scenario{vm=java, trial=0, benchmark=XOR} 1372.83 ns; ?=7.16 ns @ 3 trials
17% Scenario{vm=java, trial=0, benchmark=Ifs} 2397.32 ns; ?=16.81 ns @ 3 trials
33% Scenario{vm=java, trial=0, benchmark=Bits} 1311.75 ns; ?=3.04 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=XorShift} 1231.24 ns; ?=12.11 ns @ 5 trials
67% Scenario{vm=java, trial=0, benchmark=BitAndXor} 1446.60 ns; ?=2.28 ns @ 3 trials
83% Scenario{vm=java, trial=0, benchmark=BitAndEquals} 1492.37 ns; ?=14.62 ns @ 3 trials

  benchmark   us linear runtime
        XOR 1.37 =================
        Ifs 2.40 ==============================
       Bits 1.31 ================
   XorShift 1.23 ===============
  BitAndXor 1.45 ==================
BitAndEquals 1.49 ==================

vm: java
trial: 0

Looks like @aaronman is the winner

Upvotes: 26

Views: 5776

Answers (6)

aaronman
aaronman

Reputation: 18751

(int1 ^ int2) >> 31 == 0 ? /*on same side*/ : /*different side*/ ; This doesn't necessarily handle 0 correctly I'm not sure what you wanted to do in that case.
EDIT: also wanted to point out that if this was in c instead of java, it could be optimized further by getting rid of the == 0 because of the way that booleans work in c, the cases would be switched though

Upvotes: 14

fge
fge

Reputation: 121810

Another answer...

final int i = int1 ^ int2;

if (i == 0 && int1 == 0) {
    // both are zero
} else if (i & Integer.MIN_VALUE == Integer.MIN_VALUE) {
    // signs differ
} else {
    // same sign
}

Upvotes: 0

hatchet - done with SOverflow
hatchet - done with SOverflow

Reputation: 16257

if (int1 == 0 || int2 == 0) {
    // handle zero
} else if ((int1 >> 31) == (int2 >> 31)) {
    // same side
} else {
    // different side
}

or

if (int1 == 0 || int2 == 0) {
    // handle zero
} else if ((int1 & Integer.MIN_VALUE) == (int2 & Integer.MIN_VALUE)) {
    // same side
} else {
    // different side
}

The idea of both is the same - strip all but the sign bit, and then compare that for equality. I'm not sure which is faster, the right shift (>>) or the bitwise and (&).

Upvotes: 2

greedybuddha
greedybuddha

Reputation: 7507

Alternate answers

Compare the sign bit

return ((n >> 31) ^ (n2 >> 31) ) == 0 ? /* same */ : /* different */;

Alternate way of comparing sign bit

return (((int1 & 0x80000000) ^ (int2 & 0x80000000))) == 0 ? /* same */ : /* different */;

and I just verified but Op's code is wrong when int1 == int2. The following will always print different if they are the same.

if (int1 == 0 || int2 == 0) {
    // handle zero
} else if ((int1 ^ int2) < 0) {
    // same side
} else {
    // different side
}

Upvotes: 1

Yelko
Yelko

Reputation: 64

 int int1    = 3;
 int int2    = 4;
 boolean res = ( (int1 * int2) >= 0) ? true : false;

 System.out.println(res);

Upvotes: -4

Leeor
Leeor

Reputation: 19736

I would bitcast them to unsigned int, and xor the MSB (most-significant-bit) - much faster than any comparison (which does a subtraction) or multiplication

Upvotes: 1

Related Questions