Maximize a plus b given a xor b

Given non-negative integers $n$ and $k$, find

$$\max \{\, a + b \;:\; a \oplus b = k,\ 0 \le a,\, b \le n \,\}$$

or report that no such pair exists.

The whole solution hinges on the classic bitwise identity

Looking bit by bit: at each position the two bits $(a_i, b_i)$ contribute $a_i + b_i \in \{0, 1, 2\}$ to the sum. That contribution is $1$ exactly when the bits differ (XOR), and $2$ exactly when both are $1$ (AND). So every bit’s contribution is captured by “XOR gives $1$” plus “AND gives $2$”.

Since $a \oplus b = k$ is fixed, maximizing $a + b$ is equivalent to maximizing $c := a \wedge b$. Also note:

The bits of $a \oplus b$ and $a \wedge b$ are always disjoint.

A single bit position can either be “differing” (contributing to XOR) or “both one” (contributing to AND), never both. So whatever $c$ we pick must satisfy

Fix any $c$ with $c \wedge k = 0$. Every valid pair $(a, b)$ with $a \oplus b = k$ and $a \wedge b = c$ has the form

where $s$ is any sub-mask of the bits of $k$, and $s$ and $k \oplus s$ partition the set bits of $k$ between the two numbers. Because $c$ shares no bits with $k$, OR is the same as addition here:

In particular,

independent of $s$. The choice of $s$ only decides how the bits of $k$ are distributed between $a$ and $b$.

We still have freedom in $s$, and we should use it to make the larger of $a, b$ as small as possible. Let $h$ be the value of the highest set bit of $k$:

Since the highest bit of $k$ must land in exactly one of $s$ or $k \oplus s$,

And this is achievable: put the highest bit alone into $s$ and all other bits of $k$ into $k \oplus s$. Since the sum of all lower bits of $k$ is strictly less than $h$, the “big” side is just $h$.

Therefore the minimum possible value of $\max(a, b)$ is

and the constraint $a, b \le n$ collapses to

Special cases:

1. $k = 0$: Then $a \oplus b = 0$ forces $a = b$, and $a + b = 2a \le 2n$. Answer: $2n$.
2. $k > 0$ and $h > n$: Even the most balanced split puts the high bit above $n$. No solution.

Let $M = n - h$. We need:

Find the largest $c$ with $c \le M$ and $c \wedge k = 0$.

Equivalently, out of the bit positions that are not set in $k$, pick a subset whose value is as large as possible without exceeding $M$.

Scan bit positions from the most significant down to $0$, building $c$:

1. If the current bit of $M$ is $0$: keep that bit of $c$ at $0$ (any $1$ here would push $c$ above $M$ unless we’ve already gone strictly below, which we haven’t yet in this branch).
2. If the current bit of $M$ is $1$ and that bit is allowed (not in $k$): set it in $c$. This matches $M$ on this position and keeps us “tight”.
3. If the current bit of $M$ is $1$ but that bit is forbidden (in $k$): we cannot match $M$ here. Force this bit of $c$ to $0$. Now $c$ is strictly less than $M$ on the prefix, so every lower bit is free. Set every remaining allowed bit to $1$ and return.

If the scan finishes without ever hitting case 3, then every set bit of $M$ is allowed and we end up with $c = M$.

The reason we always prefer matching $M$’s high bits over “breaking” early is the classic power-of-two inequality

One high bit outweighs every lower bit combined. So whenever we can legally set a bit that $M$ also sets, we should; breaking below $M$ at a position where we could match would cost us $2^i$ and, in the best case, only buy back at most $2^i - 1$ from the lower positions.

Conversely, once we are forced to break (case 3), we have no reason to hold back on any lower allowed bit: we’re already strictly below $M$, so each lower allowed $1$ is a free gain.

1. If $k = 0$: output $2n$.
2. Let $h$ be the highest set bit of $k$. If $h > n$: no solution.
3. Let $M = n - h$. Greedily find the largest $c \le M$ with $c \wedge k = 0$.
4. Output $2c + k$.

Complexity: $O(\log n)$ per query.

You can find the code here.

Let $n = 13 = 1101_2$ and $k = 6 = 0110_2$.

• Highest bit of $k$: $h = 4$. Since $h \le n$, a solution exists.
• $M = n - h = 9 = 1001_2$.
• Allowed bits are those not in $k$, i.e. positions $\{0, 3, 4, 5, \dots\}$.
• Bit $3$ of $M$ is $1$ and allowed $\Rightarrow$ set it: $c = 1000_2$.
• Bits $2, 1$ of $M$ are $0$ $\Rightarrow$ skip.
• Bit $0$ of $M$ is $1$ and allowed $\Rightarrow$ set it: $c = 1001_2 = 9$.
• Answer: $2c + k = 18 + 6 = 24$.

Verification: take the optimal split $s = 4$, $k \oplus s = 2$, giving

Both are $\le 13$, $a \oplus b = 13 \oplus 11 = 6 = k$, and $a + b = 24$.

• Whenever a problem mixes XOR with addition, reach for $a + b = (a \oplus b) + 2(a \wedge b)$. It decouples the sum into two disjoint bitmasks.
• The bits of $a \oplus b$ and $a \wedge b$ are always disjoint. This is often what lets you parametrize the unknowns cleanly.
• “Largest value $\le M$ avoiding a forbidden bitmask” is a standard greedy / digit-DP template worth remembering.
• When a bound like $a, b \le n$ applies to both numbers individually, figure out which split of the XOR minimizes $\max(a, b)$. Here, it’s always the highest bit of $k$ going solo on one side.