Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$

Question

Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b "=" a \oplus b \oplus ((a \land b) \ll 1)$$ where $\oplus$ is bitwise XOR and $\land$ is bitwise AND, and $\ll$ is left-shift by 1 position. (The purpose of $((a \land b) \ll 1)$ is to simulate the "carry-bit" operation.) I was wondering "how well" this approximation worked in terms of the Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1).$

Let's make this precise.

Formal version. Let $\{0,1\}^\mathbb{N}$ denote the collection of functions $f:\mathbb{N}\to \{0,1\}$ and let $$\{0,1\}^* = \{x \in \{0,1\}^\mathbb{N}: \exists N\in\mathbb{N}(\forall k\in\mathbb{N}(k\geq N\implies x(k)=0))\}.$$ Every member of $\{0,1\}^*$ can be viewed as the binary expansion of a natural number; this is a unique correspondence. This correspondence gives rise to the addition $+:\{0,1\}^* \times \{0,1\}^* \to \{0,1\}^*$. Denote by $\ll 1$ the left-shift by one position, i.e. $\ll 1 : x \in \{0,1\}^* \to x'\in \{0,1\}^*$ where $x'(0) = 0$ and $x'(n+1) = x(n)$ for all $n\in \mathbb{N}$. We usually write $x \ll 1$ instead of $\ll 1(x)$.

For $x\in\{0,1\}^*$ we set $\text{len}(x) = \max\{k\in\mathbb{N}:x(k) = 1\}$.

For $a,b\in\mathbb{N}$ we denote by $\text{diff}(a,b)$ the Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$.

Question. Do we have $\max\{\text{diff}(a,b): a,b\in \{0,1\}^*\} < \infty$? If not, what is $\lim \sup_{n\to\infty} D_n$ where $$D_n=\frac{1}{n} \max\{\text{diff}(a,b): a,b\in\{0,1\}^*, \max\{\text{len}(a),\text{len}(b)\} = n\}$$ for $n\geq 1$?

Answer 1

The lim sup is exactly $1$. Almost certainly the exact value of $D_n$ comes from $a = (1,1,1,\ldots,1)$ and $b = (1,0,0,\ldots,0)$, and even if not, it’s off by at most $O(1/n)$ which is inconsequential. In such case we have about the maximum number of carries which are undetected by the $a \land b$. So $a+b = 2^n$ but $(a \land b) \ll 1 = 2$, so the approximate sum is $(0,0,1,1,1,\ldots,1)$, making the Hamming distance equal to $n-1$ (there are $n+1$ bits in $a+b$ and only the lowest two agree). So $D_n \ge 1 - \frac1n$.

Update: thanks to user44191’s observation, this bound is in fact precise, so $D_n = 1 - \frac1n$.