in reply to Re^3: Need a faster way to find matches
in thread Need a faster way to find matches

I love the idea of going from N^2/2 to N. Unfortunately, the valid pairs are not the bitwise negated value; it could be that one, but also other values that don't have all the possible (negated) bits set.
  • Comment on Re^4: Need a faster way to find matches

Replies are listed 'Best First'.
Re^5: Need a faster way to find matches
by kikuchiyo (Hermit) on Jan 17, 2010 at 19:17 UTC
    I don't understand then.

    You stated the condition for a match as ($A & $B) == 1 where $A and $B are (64-bit, unsigned) integers.
    Let $As = $A >> 1 and $Bs = $B >> 1.
    Isn't then the original condition equivalent to ($As & $Bs) == 0 ?

    For a given $A (and $As), what other $B (and $Bs) does satisfy that condition than $Bs = ~$As?
[reply]
[d/l]
[select]
      I ended up using your idea of shifting off the least significant bit (saved some time doing !($i1 & $i2) instead of ($i1 & $i2) == 1).

      The criteria to be in the list is complex (and I don't want to go off-topic). The numbers are highly constrained, yet once they make it to the list, I need to find all pairs of numbers which do not share any common bits (after getting rid of the one shared lsb). Below is an example of a valid pair. The bit-wise complement may or may not exist in the list. 

      #all values have been right shifted to get rid of lsb
$i1 = 0b1010_0100;
$i2 = 0b0100_1000;
#the above two numbers are a valid pair.
# yet my list may not contain either ~$i1 or ~$i2
$i1_bits_reversed = 0b0101_1011;
$i2_bits_reversed = 0b1011_0111
# the above two numbers are not a valid pair,

      [download]
      Does that example, clarify why the bitwise negation isn't a quick trick? I may be missing your approach altogether.
[reply]
[d/l]
        Yes, I see it now.

        I must have misunderstood your condition "do not share any common bits" to mean ~($i1 XOR $i2) instead of $i1 & $i2. For example, the two numbers in the first example do "share" common bits in the sense that both bits are 0. In this case the only valid value for a given $i1 would be ~$i1 and nothing else.

        However, if the condition is $i1 & $i2 == 0, then you're right, there are several possible $i2's.

        Still, you may be still better off generating the list of possible values for every existing element of the array and check those instead of blindly doing all comparisons.
[reply]

In Section Seekers of Perl Wisdom