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

Community
  • 1
  • 1
durron597
  • 31,968
  • 17
  • 99
  • 158
  • 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. – David says Reinstate Monica Jun 05 '13 at 21:29
  • @Dgrin91 Ahead of you, I was editing that in :) – durron597 Jun 05 '13 at 21:30
  • 1
    Also, shouldn't it be `(int1 ^ int2) < 0` for the same sign? – jlordo Jun 05 '13 at 21:32
  • @jlordo Sorry that was a typo – durron597 Jun 05 '13 at 21:33
  • maybe Math.signum(a)? see http://stackoverflow.com/questions/13988805/fastest-way-to-get-sign-in-java – Alex Jun 05 '13 at 21:39
  • 7
    `(int1 ^ int2) < 0` uses 2 operations which can be handled directly by hardware. It doesn't go any quicker than that. – jlordo Jun 05 '13 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 Jun 05 '13 at 21:44
  • 2
    does this work for int1 == int2? – Liviu Stirb Jun 05 '13 at 21:51
  • 1
    How about >>31 both values and compare with ==? You're adding a bitwise operation, but avoiding > or <. – hatchet - done with SOverflow Jun 05 '13 at 21:55
  • @hatchet That answer runs in exactly the same time as XOR. But it would be the best answer so far, I'd checkmark it if there are no better answers. – durron597 Jun 05 '13 at 22:00
  • Note: `(int1 ^ int2) < 0` checks that one number is negative, and the other nonnegative. You mixed that up in the question. Other note: I don't think you have a chance of beating that check. If you could get rid of the 0 check, if 0 could be handled as either positive or negative, as is more convenient, that would speed things up. – Daniel Fischer Jun 05 '13 at 22:06
  • The difference between the top three solutions is small enough, and so dependent on just a few operations, that you might consider the possibility that the rank might be different, depending on the CPU model (if your development machine is different than the target machine). In other words, the difference between your original solution and the two better ones may well be "within the noise". – hatchet - done with SOverflow Jun 05 '13 at 23:14
  • @hatchet don't be a sore loser, I doubt the CPU matters much since this is java, if you want to make the claim that the results are noise test in C and give us the results – aaronman Jun 06 '13 at 00:04
  • @hatchet also ur solution is pretty clever so I upvoted you anyway – aaronman Jun 06 '13 at 00:06
  • @aaronman - I didn't want it to look like a sore loser comment (I upvoted your answer when I saw it - I like it better than mine). But yours is faster because of minor differences in either (or both) the speed of ^ vs. >>, and x==0 vs. x==y. Those minor differences may not be universal, or at least measurably different everywhere. I don't know...maybe they are. – hatchet - done with SOverflow Jun 06 '13 at 00:10
  • @hatchet, sorry I was just kidding, the only reason I would say mine is actually faster is because in c I can just get rid of the `==` whereas in your solution you cannot do that – aaronman Jun 06 '13 at 00:15
  • @aaronman I wonder if it makes sense to replace all `> 0` with `>> 31 == 0` everywhere in all code. Obviously you couldn't do it for `>` not-zero, but it still might work – durron597 Jun 06 '13 at 13:54
  • @durron597 well I wouldn't expect java to do that but I wouldn't be suprised if a c++ compiler does something like that – aaronman Jun 06 '13 at 14:42
  • Add `Integer.isPositive(int num)` to the api, haha – durron597 Jun 06 '13 at 14:58
  • 1
    In case someone is tempted to assume the relative performance of these various techniques applies to other languages as well...don't. For example the speed rank of the top three answers here is the opposite in C#. x^y>0 is fastest, x>>31==y>>31 is second, and x^y>>31==0 is third. Which one is fastest depends on the language/compiler and the optimizations it makes under the covers. – hatchet - done with SOverflow Jun 09 '13 at 13:35

6 Answers6

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

aaronman
  • 18,343
  • 7
  • 63
  • 78
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 (&).

hatchet - done with SOverflow
  • 15,919
  • 5
  • 47
  • 57
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

Leeor
  • 19,260
  • 5
  • 56
  • 87
  • 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](http://stackoverflow.com/questions/9578639/best-way-to-convert-a-signed-integer-to-an-unsigned-long) – Leeor Jun 05 '13 at 21:56
  • 1
    There are no unsigned ints in Java – durron597 Jun 05 '13 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 Jun 05 '13 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
}
greedybuddha
  • 7,488
  • 3
  • 36
  • 50
  • 1
    But that's just the solution OP had. – zw324 Jun 05 '13 at 21:46
  • alternate answer that I believe should be fast and correct. Which I've now seen that Ops code is not – greedybuddha Jun 05 '13 at 22:01
  • Okay it should be `<=` or do `> 0` -> different side first – durron597 Jun 05 '13 at 22:03
  • True, but that will slow it down a bit, how do my answers compare on your benchmark? – greedybuddha Jun 05 '13 at 22:05
  • Mine I, believe is faster cause I only use right shift once whereas you do it twice, I changed yours – aaronman Jun 05 '13 at 22:22
  • mine also deals with 0 though :). I'd like to actually test, but I'm having issues getting caliper running – greedybuddha Jun 05 '13 at 22:27
  • @greedybuddha caliper 1.0-beta doesn't work on Windows as far as I can tell. I fought with it for an hour before I went back to [0.5-rc1](http://search.maven.org/#artifactdetails|com.google.caliper|caliper|0.5-rc1|jar) – durron597 Jun 06 '13 at 13:55
  • I got it working after like 10 minutes after I posted this. I was thrown off by you using 0.5, which had different classes than 1.0. but it's all good now :) thanks for introducing me to a good profiling system! – greedybuddha Jun 06 '13 at 13:57
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
}
fge
  • 119,121
  • 33
  • 254
  • 329
-4
 int int1    = 3;
 int int2    = 4;
 boolean res = ( (int1 * int2) >= 0) ? true : false;

 System.out.println(res);
Yelko
  • 64
  • 6