in reply to
Need a faster way to find matches
I may be missing something here, but if you are only testing the least significant bit aren't you simply testing whether the integers are even or odd?
Since there are only two possible groups (even or odd), it seems overkill to use a hash to store all possible combinations of integers in each group. Why not store the odd numbers (since you want the least significant bit set) in an array, then compute the possible combinations afterwards? See Math::Combinatorics for one option.
Update: If you need the results in a hash, it could be populated while constructing the combinations of odd numbers. I suspect that most of the time (and memory) required for your routine is spent on the storage steps, not on the bitwise comparison itself.
Update 2: I misread the question, thinking that the comparison only included the last bit. As BrowserUK notes below, this is not correct. Apologies for the misunderstanding.