Minimum number of AND operations to make all array elements zero

This seems to me like the set cover problem. We need to find the smallest subset that covers zeros in every position. Once that subset is found, the "absolute" zero that's generated can be used to convert other elements to zero. In the example below, any of the three elements in the subset can be used to become the first zero.

1001
0101<
0011<
1110<
0111

If the problem has a solution for a given input, you can perform these operations:

1. Choose an index i between [0,n-1](assuming array indexing is zero based).

2. For every j between 0 and n that is not i, perform a_i <- a_i & a_j. At this point you are guaranteed a_i equals 0, otherwise the problem is unsolveable because you performed bitwise and on all items in the array.

3. For every j between 0 and n that is not i, perform a_j <- a_i & a_j. This performs and on all items in the array with 0, making them 0 also.

You perform the and operation n-1 times for the first loop and n-1 times for the second loop, so in total 2n-2 and operations.

Edit:

This is assuming you cannot look at the values in the array.

My guess is that you can get the needed speedup by making your DP table sparse. We can think of the resulting algorithm as doing a breadth-first search from 2^D-1 to 0 on a graph where the nodes are 0..2^D-1 and the edges go from x to x&y where y is an array element. In fact, due to the commutativity/associativity of bitwise AND, we can tighten the edge set by requiring that x&y clear the lowest bit set in x. In the Python code below, this is achieved somewhat efficiently by using a map zero_index, but in C I would use an array (and replace the sets with bitmaps or arrays as appropriate).

import collections
import random


def min_and(seq):
    lst = list(seq)
    zero_index = collections.defaultdict(lambda: set(lst))
    for x in lst:
        y = x
        while y:
            zero_index[y & ~(y - 1)].discard(x)
            y &= y - 1
    visited = set()
    fringe = set(lst)
    i = 0
    while 0 not in fringe:
        visited.update(fringe)
        fringe = {
            x & y
            for x in fringe for y in zero_index[x & ~(x - 1)]
            if x & y not in visited
        }
        i += 1
    return i + len(lst) - 1


print(min_and(
    random.randrange(2**18) | random.randrange(2**18) | random.randrange(2**18)
    for i in range(100)))