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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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