If they are all odd numbers, then their LSB is always 1, isn't it?
Why don't you just drop that bit then, and test for the bitwise ANDs of the resulting numbers being 0?
my @chopped_array = map { $_ >> 1 } @original_array;
my %result;
foreach my $i1 (0..$#chopped_array) {
foreach my $i2 ($i1..$#chopped_array) {
$result{ $original_array[$i1] } = $original_array[$i2] unless
+$chopped_array[$i1] & $chopped_array[$i2];
}
}
This algorithm is still quadratic, though - you still
need to do N^2/2 comparisons for an N-sized array.
But what if you build an auxiliary hash out of those lsb-shifted-off integers, then for every value simply check whether the bitwise negated value is present among the hash keys?
my %hash = map { ($_ >> 1) => 1 } @original_array;
my %result;
foreach (keys %hash) {
$result{($_ << 1) + 1} = ~($_ << 1) if $hash{ ~$_ };
}
Or something like this.
Beware of bugs, as I have not tested the code above, nor have I proved it correct :) | [reply]
[d/l]
[select] |
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.
| [reply] |
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] |