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


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.

Replies are listed 'Best First'.
Re^2: Need a faster way to find matches
by BrowserUk (Patriarch) on Jan 17, 2010 at 10:30 UTC
    only least significant bit overlaps

    Is quite different to just odd or even:

    $x = 0b1111_1110_1101_1100_1011_1010_1001_1000_0111_0110_0101_0100_001 +1_0011;; $y = 0b0000_0001_0010_0011_0100_0101_0110_0111_1000_1001_1010_1011_110 +0_1101;; printf "%064b\n", $x & $y;; 0000000000000000000000000000000000000000000000000000000000000001

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Need a faster way to find matches
by CountZero (Bishop) on Jan 17, 2010 at 09:05 UTC
    Math::Combinatorics will not do the trick: it will give you all the permutations of an array or list, but cannot do nPk where n < k. Use Algorithm::Permute for that.

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

Re^2: Need a faster way to find matches
by remzak (Acolyte) on Jan 17, 2010 at 13:30 UTC
    BrowserUk gave a great example... I am really looking for the integers in the list that do not share any bits except the lsb.