Problems? Is your data what you think it is? PerlMonks

### Re^5: Need a faster way to find matches

by kikuchiyo (Pilgrim)
 on Jan 17, 2010 at 19:17 UTC ( #817887=note: print w/replies, xml ) Need Help??

in reply to Re^4: Need a faster way to find matches
in thread Need a faster way to find matches

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?

Replies are listed 'Best First'.
Re^6: Need a faster way to find matches
by remzak (Acolyte) on Jan 18, 2010 at 00:25 UTC
I ended up using your idea of shifting off the least significant bit (saved some time doing !(\$i1 & \$i2) instead of (\$i1 & \$i2) == 1).

The criteria to be in the list is complex (and I don't want to go off-topic). The numbers are highly constrained, yet once they make it to the list, I need to find all pairs of numbers which do not share any common bits (after getting rid of the one shared lsb). Below is an example of a valid pair. The bit-wise complement may or may not exist in the list.

```#all values have been right shifted to get rid of lsb
\$i1 = 0b1010_0100;
\$i2 = 0b0100_1000;
#the above two numbers are a valid pair.
# yet my list may not contain either ~\$i1 or ~\$i2
\$i1_bits_reversed = 0b0101_1011;
\$i2_bits_reversed = 0b1011_0111
# the above two numbers are not a valid pair,
Does that example, clarify why the bitwise negation isn't a quick trick? I may be missing your approach altogether.
Yes, I see it now.

I must have misunderstood your condition "do not share any common bits" to mean ~(\$i1 XOR \$i2) instead of \$i1 & \$i2. For example, the two numbers in the first example do "share" common bits in the sense that both bits are 0. In this case the only valid value for a given \$i1 would be ~\$i1 and nothing else.

However, if the condition is \$i1 & \$i2 == 0, then you're right, there are several possible \$i2's.

Still, you may be still better off generating the list of possible values for every existing element of the array and check those instead of blindly doing all comparisons.

Create A New User
Node Status?
node history
Node Type: note [id://817887]
help
Chatterbox?
 [LanX]: Oh I see, userDict should have been declared in n outer scope ... [LanX]: an [LanX]: strange python accepts this? [LanX]: no previous userDict?

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (13)
As of 2018-03-20 18:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (257 votes). Check out past polls.

Notices?