**Motivation.** In their [paper](https://www.aumasson.jp/data/papers/AJN14a.pdf) 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](https://en.wikipedia.org/wiki/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$?



Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 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$.


