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.
- Create the hash from the list.
- get a list of all the numbers with the 2**1 bit set.
- remove those numbers from the hash.
- compare them against the numbers in the hash
- 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}++;
}
}
}
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.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|