The secret is that there are only 63 bits and that any number with a certain bit set can not 'match' any number with that same bit set.

So all you need to do is get a list of all the elements with a bit set and compare them with all of the numbers with out that bit set.

By using a hash in place of the list we can do this pretty efficiently.

  1. Create the hash from the list.
  2. get a list of all the numbers with the 2**1 bit set.
  3. remove those numbers from the hash.
  4. compare them against the numbers in the hash
  5. repeat for 2**2 through 2**63
You do need to fix up the generated hash afterwards, as it will on have half of the keys in it. 
use strict;

use vars qw (@LongListOfIntegers %bighash %MatchedIntegers);
my $x = 20;
push( @LongListOfIntegers, int( rand( 2**8 ) ) ) while ( $x-- );
$bighash{$_} = 0 for @LongListOfIntegers;

for my $bit (1..63) {
    my $n = 2 ** $bit;
    my @slist = grep( { ($_ & $n) } keys %bighash);
    delete $bighash{$_} for @slist;
    my $x = 0;
    for my $i (@slist) {
        for my $j (keys %bighash) {
            $MatchedIntegers{$i}{$j}++ if ( ( $i & $j ) == 1 );
            $x++ if ( ( $i & $j) == 1 );
        }
    }
}

normalize(\%MatchedIntegers);

use Data::Dumper;
print Dumper \%MatchedIntegers;

sub normalize
{
    my $hash = shift;
    for my $o (keys %{$hash}) {
        for my $i (keys %{$hash->{$o}}) {
            $hash->{$i}{$o}++;
        }
    }
}

[download]
note: It is also easy to split the problem up into 63 problems and use POE or some such to run each on a separate processor -- if you have 63 processors on your computer.
-- gam3
A picture is worth a thousand words, but takes 200K.

In reply to Partition in to 63 parts by gam3
in thread Need a faster way to find matches by remzak

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.