2

What is the fastest way to find if two numbers have the same sign considering that the sign can either be positive, negative or zero.

Commonly, you can say two numbers have same signs with this:

Math.signum(int1) == Math.signum(int2);

You can optimize this by using this:

int1 ^ int2 >= 0;

however, this is making the assumption that zero is positive. What are some ways that will return true including zero.

Some examples of errors would be:

a = 0; b = 1;
boolean test = a ^ b >= 0

where test would yield true instead of false.

I ran some testbenchs and found that the bitwise function returns values faster by nearly 4 orders of magnitude. Since this is a function I will be using in a very large tree for every node, I need to optimize this as much as possible.

I would post an attempted solution, but I can't find one that beats the original one.

Edit: I realize there is a similar problem found here: Fastest way to check if two integers are on the same side of 0 I am asking if there is a way to find if signs are the same INCLUDING zero. so comparisons between 1 and 1 is true, -1 and -1 is true, 0 and 0 is true, 0 and 1 is false, 0 and -1 is false, etc. This is not the same thing as the question asked above!

Community
  • 1
  • 1
Michael Choi
  • 610
  • 5
  • 22
  • Possible duplicate of [Fastest way to check if two integers are on the same side of 0](http://stackoverflow.com/questions/16950163/fastest-way-to-check-if-two-integers-are-on-the-same-side-of-0) – Andremoniy Feb 07 '17 at 21:46
  • 1
    Let it go. You cannot be interested in efficiency and choose to develop in java. For efficiency, choose a language like either assembler, c, or (perhaps) fortran – DwB Feb 07 '17 at 21:46
  • Here is answer for question I've linked above: `(int1 ^ int2) >> 31 == 0 ? /*on same side*/ : /*different side*/ ` – Andremoniy Feb 07 '17 at 21:46
  • @Andremoniy I already checked this solution. This does not handle the case for zero as I mentioned in the title. – Michael Choi Feb 07 '17 at 21:47
  • 4
    @DwB, we're not in 1996 anymore. – Mick Mnemonic Feb 07 '17 at 21:47
  • With compiler optimisation and CPU optimisation, what appears to be on paper the faster solution may not end up being such in practice. – AntonH Feb 07 '17 at 21:47
  • Does it have to work for `Integer.MIN_VALUE`? – harold Feb 07 '17 at 21:49
  • @AntonH I ran a test bench of 100,000 comparisions between the two operations and the bitwise operation significantly performed better (by 1000x fold). Obviously if I were to include the zero case, it would not be so great but I wanted to try. I decided to try and optimize this comparison since this was a hotspot for the most runtime in a particular function. – Michael Choi Feb 07 '17 at 21:50
  • @harold no. This only has to work for very small numbers (-8 to 8) – Michael Choi Feb 07 '17 at 21:51
  • @DwB do you know of a way to accomplish this goal in c or c++? this problem is not strictly for java, though it would be convenient. – Michael Choi Feb 07 '17 at 21:52
  • I suspect it will be a variation of this: ((char1 ^ char2) & 0x80) == 0 adjust the 0x80 for the size of the actual xor values. specifically, bitwise xor the values then mask off every bit except the sign bit. This is not sufficient if you can have positive-zero and negative-zero values and you want to consider positive-zero equal to negative zero. I assume that the straight mask is faster than a 31 bit shit. Not sure and it may depend on hardware. – DwB Feb 07 '17 at 22:02

3 Answers3

2

Here's what I came up with:

private static boolean signcmp(int x, int y) {
    return ((( x >> 31) | (-x >>> 31)) ^ (( y >> 31) | (-y >>> 31))) == 0; 
}
Matthew McPeak
  • 17,705
  • 2
  • 27
  • 59
  • `(a ^ b) == 0` is the same thing as `a == b`, I hope the JIT compiler knows that too, but it might still be nicer idk – harold Feb 07 '17 at 22:08
  • And I must say I'm really surprised the difference is that big, they're really just minor variants of each other. OR vs SUB, SHR vs SAR, it shouldn't really matter – harold Feb 07 '17 at 22:11
  • @harold its probably because you gave a part of the solution and I didn't implement it well enough. The largest difference I can see is the OR vs SUB. do they really take the same amount of time? – Michael Choi Feb 07 '17 at 22:14
  • @MichaelChoi they're equally fast on any machine I know about, in hardware OR is faster of course but you're not writing VHDL here. Perhaps you timed them unreliably? You could try if switching the order of the benchmarks makes a difference for example. – harold Feb 07 '17 at 22:15
  • @harold yeah I just tried switching the order which had inconsistent results. I am not really that great at coding yet so I think my test benches were not as accurate. Running them alone yields nearly identical results and I am assuming deviations are simply a result of background tasks. – Michael Choi Feb 07 '17 at 22:18
1

You could use an integer version of signum, such as (not tested):

int signum(int x) {
    int m = x >> 31;
    int neg_m = -x >> 31;
    return m - neg_m;
}

Here m will be -1 iff x < 0 (0 otherwise), and neg_m will be -1 iff x > 0 (ignoring Integer.MIN_VALUE). Their difference is,

  • -1, for x < 0
  • 0, for x == 0
  • 1, for x > 0

It also gives 0 for Integer.MIN_VALUE, but since that never occurs in your case that shouldn't matter.

harold
  • 61,398
  • 6
  • 86
  • 164
  • similar answer can be found @Matthew_McPeak This is chosen as the answer due to better clarity. – Michael Choi Feb 07 '17 at 22:20
  • Also, I believe my answer works for `Integer.MIN_VALUE`, due to use of unsigned right shift on the negative values, not that it matters for the OP. – Matthew McPeak Feb 07 '17 at 22:21
  • @MatthewMcPeak thanks to the OR-logic, I'd say, but that's enabled by the unsigned shift so it's sort of back to that.. For example the unsigned shift together with addition would be exactly equivalent to what I came up with – harold Feb 07 '17 at 22:25
0

Without having benchmarked this, I doubt whether you could do any better than

sameSign = a < 0 ? b < 0 : ( a == 0 ) == ( b == 0 );
Dawood ibn Kareem
  • 77,785
  • 15
  • 98
  • 110