26

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

20
  • 4
    Just out of curiosity, how are you checking the speed? Also, I would recommend not putting the zero case first, as it is presumably the least likely. Commented Jun 5, 2013 at 21:29
  • 1
    Also, shouldn't it be (int1 ^ int2) < 0 for the same sign?
    – jlordo
    Commented Jun 5, 2013 at 21:32
  • 7
    (int1 ^ int2) < 0 uses 2 operations which can be handled directly by hardware. It doesn't go any quicker than that.
    – jlordo
    Commented Jun 5, 2013 at 21:40
  • 1
    I bow to your brilliant question, it should be tagged as "answer trap". Everyone took a stab at this question seems to be getting downvoted. Perhaps yours is the one solution?
    – zw324
    Commented Jun 5, 2013 at 21:44
  • 2
    does this work for int1 == int2? Commented Jun 5, 2013 at 21:51

6 Answers 6

14

(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

5
  • I'm pretty sure this is the fastest answer. I plan to checkmark it a little later on unless someone comes up with something better.
    – durron597
    Commented Jun 5, 2013 at 22:41
  • Then someone should give me a cookie
    – aaronman
    Commented Jun 5, 2013 at 22:42
  • 1
    I like the way your bits shift ;) Commented Jun 6, 2013 at 1:12
  • 3
    Why shift at all? (int1 ^ int2) >= 0 ? same : different should yield the exact same result
    – Durandal
    Commented Jun 21, 2013 at 15:24
  • @Durandal i was thinking in c my answer where u could just get rid of == but if you want check the speeds urself i did no testing just answered the question
    – aaronman
    Commented Jun 21, 2013 at 15:35
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 (&).

3
  • @durron597 - I've put the bitwise and version back in. Commented Jun 5, 2013 at 22:30
  • The second answer is the same as @greedybuddha's answer, er, no it isn't, but I already changed his to that haha. Big edit coming up.
    – durron597
    Commented Jun 5, 2013 at 22:30
  • Can't cast int to a bool, sorry
    – durron597
    Commented Jun 5, 2013 at 22:39
1

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

3
  • 1
    the concept remains though, i'm no java expert but i'm fairly sure you can do something like: (int1 & 0x8000000000000000L) ^ (int2 & 0x8000000000000000L) , give or take syntax issues and based on your integer size of course. It's mentioned here as well - Best way to convert a signed integer to an unsigned long
    – Leeor
    Commented Jun 5, 2013 at 21:56
  • 1
    There are no unsigned ints in Java
    – durron597
    Commented Jun 5, 2013 at 22:00
  • ok, so aside from casting, how is this different than what was suggested above? switching the brackets and saying (int1 ^ int2) & 0x8000000000000000 is quite the same as (int1 ^ int2) >> 31. I call dibs :)
    – Leeor
    Commented Jun 5, 2013 at 22:51
1

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
}
8
  • 1
    But that's just the solution OP had.
    – zw324
    Commented Jun 5, 2013 at 21:46
  • alternate answer that I believe should be fast and correct. Which I've now seen that Ops code is not Commented Jun 5, 2013 at 22:01
  • Okay it should be <= or do > 0 -> different side first
    – durron597
    Commented Jun 5, 2013 at 22:03
  • True, but that will slow it down a bit, how do my answers compare on your benchmark? Commented Jun 5, 2013 at 22:05
  • Mine I, believe is faster cause I only use right shift once whereas you do it twice, I changed yours
    – aaronman
    Commented Jun 5, 2013 at 22:22
0

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
}
-4
 int int1    = 3;
 int int2    = 4;
 boolean res = ( (int1 * int2) >= 0) ? true : false;

 System.out.println(res);
3
  • This doesnt solve the problem though, you need to know which one it is - zero or same side Commented Jun 5, 2013 at 21:36
  • 3
    Performance aside, this doesn't always work. See http://ideone.com/2QkTyK
    – jlordo
    Commented Jun 5, 2013 at 21:38
  • 4
    Now try: int int1 = 1200000000; int int2 = 1500000000;
    – durron597
    Commented Jun 5, 2013 at 21:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.