-1

We have two pairs of numbers. The first pair consists of a1, a2 and the second pair consists of b1, b2. We wish to determine if any element of a is in b, or vice versa. This is simple enough:

int a1, a2, b1, b2;

// is it possible to do better than this:

boolean hasOverlap = a1 == b1 || a1 == b2 || a2 == b1 || a2 == b2;

The question is, is it theoretically possible to do this faster? Perhaps through some clever use of bitwise arithmetic?

EDIT FOR CLARITY: For specificity, imagine we are trying to optimize a java program.

Bonus question

Assuming we had an arbitrary number of pairs, instead of just two pairs. You could imagine an array of 100 arrays of length 2. What is the most efficient to remove any pair from that list if that pair contains an element that appears in another pair on the list?

So for example: [[1,2], [3,4], [2,5]] would be reduced to [[3,4]]

Jonah
  • 15,806
  • 22
  • 87
  • 161
  • 2
    What is the context here? To do it better/faster are you assuming we are performing this algorithm on a processor, or just conceptually where we are measuring the number of logical steps involved, or are we trying to reduce the number of operators used...? I'm trying to figure out why you are suggesting a bit-wise comparison might be faster than the logical comparisons. – BlackVegetable May 07 '13 at 14:54
  • Are the numbers in the pairs bounded or do you need to support arbitrarily large values? – Rup May 07 '13 at 14:55
  • Hey guys, for specificity let's say the context is a java program, and these are int values – Jonah May 07 '13 at 15:11
  • I've edited the original question to be clearer. I would appreciate comments from anyone downvoting so I can continue to improve the question. – Jonah May 07 '13 at 15:26
  • Are all of the pairs ordered? – beaker May 07 '13 at 16:04
  • @beaker, no they are not. – Jonah May 07 '13 at 16:13

3 Answers3

0

The first question is nonsensical from an algorithmic point of view because every solution will have the same complexity (namely O(1)).

For the bonus question, this is equivalent to the problem of finding duplicates in a list (if a number appears twice, just check that it appears in different pairs) and can be done in O(n*Log(n)) by sorting the list and then scanning it for conscutive numbers equal or in O(n) using a hashset of previously seen numbers.

Thomash
  • 6,339
  • 1
  • 30
  • 50
  • 2
    I wouldn't say the first question is *nonsensical* per-se. Even two O(1) algorithms can have very different run-time performance. – BlackVegetable May 07 '13 at 15:03
  • @BlackVegetable, indeed, and that was the question i was getting at. Sorry for not being clearer in the OP – Jonah May 07 '13 at 15:13
0

See the following answer for the reason why bit-wise operations CAN be faster in Java than logical operations: https://stackoverflow.com/a/11052460/758446

Thus, let's transform the original logical operations into bitwise operations:

boolean hasOverlap = a1 == b1 || a1 == b2 || a2 == b1 || a2 == b2;

boolean hasOverlap = !(a1 ^ b1) | !(a1 ^ b2) | !(a2 ^ b1) | !(a2 ^ b2);

Note that this is mixing C and Java style bit-wise operations, won't exactly compile in Java. If anyone has tips for making this compile, please comment. It has been a while since I have done bit manipulation in Java.

Community
  • 1
  • 1
BlackVegetable
  • 12,594
  • 8
  • 50
  • 82
0

Working similarly to what @BlackVegetable has, but performing an explicit comparison to 0 since java won't make that conversion for us:

boolean hasOverlap = ((a1 ^ b1) == 0) | ((a1 ^ b2) == 0) | ((a2 ^ b1) == 0) | ((a2 ^ b2) == 0);

Here, the use of the bitwise or | should, I think, only be used if you have a good reason to use it. You miss out on short circuiting, which seems very likely to have a larger impact on performance than any other gains from it, compared to:

boolean hasOverlap = ((a1 ^ b1) == 0) || ((a1 ^ b2) == 0) || ((a2 ^ b1) == 0) || ((a2 ^ b2) == 0);

Since it is more efficient generally to compare to 0, so there may be an efficiency gain there. I seriously doubt it, though, since I'm sure the folks designing the JVM would have worked out that they could implement int == int as int ^ int == 0.

This one seems much more interesting to me:

boolean hasOverlapmul = ((a1 ^ b1) * (a1 ^ b2) * (a2 ^ b1) * (a2 ^ b2))==0;
femtoRgon
  • 32,893
  • 7
  • 60
  • 87