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.