1. You can save a small amount by removing a level of scope:

   foreach my $i1 (@LongListOfIntegers) {
       ($i1 & $_)==1 and undef $MatchedIntegers{$i1}{$_} 
            foreach @LongListOfIntegers;
   }
   [download]

2. A little more by use integer;

   foreach my $i1 (@LongListOfIntegers) {
       use integer;
       ($i1 & $_) == 1 and undef $MatchedIntegers{$i1}{$_} 
            foreach @LongListOfIntegers;
   }
   [download]

3. And if the values are evenly distributed, potentially save 75% of the runtime, by pre-filtering out any even values:

   @LongListOfIntegers = grep $_ &1, @LongListOfIntegers;
   foreach my $i1 (@LongListOfIntegers) {
       use integer;
       ($i1 & $_) == 1 and undef $MatchedIntegers{$i1}{$_} 
            foreach @LongListOfIntegers;
   }
   [download]

Beyond that, any kind of categorisation of the values by the bits they have set (other than the LSB) will take far longer to set up.

It even seems unlikely that you could save much time by moving this into (Inline)C, given you want a hash as the result. To be honest 2 seconds for 16 million comparisons doesn't seem too bad.

Update: There's probably no need to have results for $x & $y and $y & $x in the hash, and even if there is, there's no need to test both. So,

@LongListOfIntegers = grep $_ &1, @LongListOfIntegers;

foreach my $i1 ( 0 .. $#LongListOfIntegers) {
    use integer;
    my $v = $LongListOfIntegers[ $i1 ];
    ($v & $_) == 1 and undef $MatchedIntegers{$i1}{$_} 
        foreach @LongListOfIntegers[ $i1+1 .. $#LongListOfIntegers ];
}
[download]

Will save a bit more, though not as much as you'd think.