How to create a special binary tree

I wish to index some data where the key is a ulong. This ulong (64 bits) represents a combo of products, where each bit of the ulong is a Product in the combo.

So if we get a ulong Key of value 3. That's really 1 + 2. That means that products 1 and 2 are present in the combo.

ulong Combo1 = 1 | 2;
ulong Combo2 = 1 | 4 | 8;

If I wish to know if Combo1 shares any product with Combo2 I could simply do this:

if((Combo1 & Combo2) != 0)
{
  //They share at least 1 product
}

This is very nice and fast, but it gets difficult if I have:

List<ulong> Combos = new List<ulong>();

And in it over 1 million Combo Keys (the key represents the products used).

How can I index this list of ulongs so that I can loop it and do the following:

foreach(ulong combo in Combo开发者_如何学编程s)
{
  //Find all the combos in Combos where no product is shaded
  List<ulong> WorksWith = GetFromIndexOrTree(combo);
  foreach(ulong combo2 in WorksWith)
  {
    //Use
  }
}

private List<ulong> GetFromIndexOrTree(ulong combo)
{
  //magic index or tree
}

Thanks a lot for your help and for the comments.

Say I am a combo with products (red, blue, and white). I wish to find all combos that don't have any or all of my products (red, blue and white). So I shall find a combo with (yellow), (green, yellow), (green, black)...

Let

    S   be the set of products.

    C ⊂ P(S)   the set of combos.

    F(p) = { c ∈ C | p ∉ c }   the set of all combos c ∈ C that do not contain the product p ∈ S.

Then

    G(X) = ∩_p∈X F(p)

gives the set of combos where no combo contains any product p in the set of products X ⊂ S.

C#

List<ulong> combos = new List<ulong> { 1 | 2, 1 | 4 | 8 };

Dictionary<int, List<ulong>> dict = Enumerable
    .Range(0, 64)
    .ToDictionary(i => i, i => combos
        .Where(combo => ((1UL << i) & combo) == 0)
        .ToList());

ulong input = 1 | 2; // find all combos that don't have product 1 or 2

List<ulong> result = Enumerable
    .Range(0, 64)
    .Where(i => ((1UL << i) & input) != 0)
    .Select(i => dict[i])
    .Aggregate((a, b) => Enumerable
        .Intersect(a, b)
        .ToList());