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

Question

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:

• XOR: Original answer with bugfix
• Ifs: Obvious ((&&)||(&&)) solution
• Bits: @hatchet's solution (>>31) == (>>31)
• BitAndXor: @greedybuddha's solution (0x80000000)
• BitAndEquals: @greedybuddha's solution modified to use == not ^
• XorShift: @aaronman's solution (^)>>31 == 0

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

Answer 1

(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

Answer 2

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 (&).