A nice form of a given function

Question

First let, $\oplus(a_1,a_2,\ldots,a_n)$ denote the bitwise xor of $a_1,a_2,\ldots,a_n$. Define the function $\Delta(a_1,a_2,\ldots,a_n)$ to be the maximum value of $a_i - \oplus(a_1,a_2,\ldots,a_{i-1},a_{i+1},\ldots,a_n)$ over $1 \leq i \leq n$. Is there a nice form for $\Delta$ or a way to simplify its definition?

Answer 1

I think it's slightly simpler to define $\Delta(a_1,a_2,\ldots,a_n)$ as the maximum value of $a_i - \left(a_i \oplus \bigoplus_{j=1}^n a_j\right)$. Then it becomes obvious that, provided the context is clear, the sum can be extracted as $k$ and we want $\max \{a_i - (a_i \oplus k)\}$.

Define $\delta_i = a_i - (a_i \oplus k)$ and consider a bit position $b$ (corresponding to value $2^b$). It is set in $k$ iff there are an odd number of $a_i$ in which it is set. Consider two cases:

1. Bit $b$ is set in $k$: it contributes $2^b$ towards $\delta_i$ for each $a_i$ in which it is set, and $-2^b$ towards $\delta_i$ for each $a_i$ in which it is clear.

2. Bit $b$ is clear in $k$: it contributes $0$ towards $\delta_i$ regardless of whether it is set or clear in $a_i$.

In tabular form: $$\begin{array}{ccc}a & k & a - (a\oplus k)\\ 0 & 0 & 0 \\ 0 & 1 & -1 \\ 1 & 0 & 0 \\ 1 & 1 & 1\end{array}$$

Since $2^b = 1 + \sum_{k = 0}^{b-1} 2^k$, an $a_i$ which has the highest set bit of $k$ but none of the others is going to give a larger $\delta_i$ than an $a_i$ which doesn't have the highest set bit of $k$ but does have all of the others. So if we choose $j$ to maximise $a_j\, \& \, k$ (bitwise AND) then that $j$ will also maximise $\delta_j$, and $\Delta(\ldots) = \delta_j$.