Let's look at the numbers as bitstrings of length $m$. For a number $x$, let $x^c$ be a number that has flipped binary representation.

For example, for $m=5$ and $x=13$ it follows $x^c=18$ because $x={01101}_2$ and $x^c={10010}_2$. Exactly $x^c$ would be the ideal candidate for the biggest Hamming distance with $x$, but $x^c$ is not necessarily a part of $a$.

Let us describe two possible solutions:

Solution 1

First solution is based on the fact that

$${\displaystyle \underset{y\in a}{max}hamming(x,y)=m-\underset{y\in a}{min}hamming(x^c,y)}$$

Intuitively, we want a number as similar to $x^c$ as possible.

Let us try to calculate the minimal Hamming distance for every number in $[0,2^m-1]$. For every number that appears in $a$ it is $0$. It leads us to a BFS solution, where each number in $[0,2^m-1]$ is a node in our graph and the edges represent changing exactly one bit. In a graph constructed in such a fashion Hamming distance between two numbers is exactly the length of shortest path between corresponding nodes. So we start BFS algorithm with every number from $a$ in our queue and we will get the desired minimal distances.

Solution 2

Second solution is based on dynamic programming. Let $popcount(x)$ be the number of ones in the binary representation of $x$. The solution will be based on the following identity:

$${\displaystyle hamming(x,y)=popcount(x)+popcount(y)-2\cdot popcount(x\mathrm{\&}y)}$$

Intuitively, each one in the binary representation of each number contributes $1$ to Hamming distance, but then each common one decreases it by $2$.

We want to calculate $dp(mask)$ - maximum number of ones for some number in $a$ but each one that is not in mask we penalize by $2$. Formally,

$${\displaystyle dp(mask)=\underset{x\in a}{max}(popcount(x)-2\cdot popcount(x\mathrm{\&}mas{k}^c))}$$

Then, the solution for some $x$ will be given as $popcount(x)+dp(x^c)$. The above $dp$ can be calculated with standard dp with bitmasks methods.

Complexity of both solutions is $\mathcal{O}(2^m\cdot m)$.