http://qs321.pair.com?node_id=817901

in reply to Need a faster way to find matches

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}++;
}
}
}