Uniquely identifying bits


Query: Given $ m$ unique integers smaller than $ 2^n$ , can we keep at most $ k$ the same bits of each number to uniquely identify them?

Is this problem NP-Hard?

For example, given the $ 4$ unique numbers smaller than $ 2^3$

011 100 101 110  ^^ 

The numbers are still unique if we remove the leftmost bit from each number. So for $ k = 2$ , the answer is yes: we keep bits {0, 1} (the rightmost bit is here defined as the bit with index 0).


I want to solve the above problem as a precomputation step for integers less than 20 bits, so for my application an exponential algorithms could be allowed. Then it would be great to minimize $ k$ and then break ties in such a way that the number of gaps between the indices that are kept is minimized. For example, {0, 1, 2, 5, 7} has two gaps: between 2 and 5 and between 5 and 7. This precomputation should lead to a great hash function for a set of integers. In my application the sets of integers don’t change later.