Re: [Algorithms] pattern search for large integer

[Robert D. <bli...@go...>]

> I have a large list of integers; each integer is of 128-bit in size.
> How to answer this question efficiently:
> 
> find those integers with bit-X equals to 1, bit-Y equals to 0, and
> bit-Z equals to 1 (0<=X<Y<Z<=127).  ie, find integers in a large list
> with bit pattern of "*1*0*1*", where '1', '0', and '1' appears at
> fixed bit position X, Y, and Z.  The values of X, Y, Z are arbitrary
> between [0,127] and have no observable pattern.
> 
> The brute-force method of iterating through the list via bit-mask
> check works, but it's O(n), and not practical if the list size is in
> millions and there're multiple bit patterns to be matched on the same
> integer list.
> 
> Any faster algorithm?

If your input data was sorted then you could do much better simply using
binary searches.

As others have mentioned, it really depends on what you plan to do with it
... Is this a static list of integers, or one generated dynamically which is
changing all the time, or one which is slowly being added to ?
Does the order of the data matter to you ?
Do you have limited storage for additional data ?