Distancia de Hamming entre $a+b$ y $a \oplus b \oplus ((a \land b) \ll 1)$

Question

Motivación. En su artículo sobre el esquema criptográfico NORX, los autores utilizan una rápida aproximación de + mediante operaciones a nivel de bits (ocupando menos ciclos de CPU que la suma real) utilizando la fórmula $$a+b "=" a \oplus b \oplus ((a \land b) \ll 1)$$ donde $\oplus$ es XOR a nivel de bits y $\land$ es AND a nivel de bits, y $\ll$ es corrimiento a la izquierda en 1 posición. (El propósito de $((a \land b) \ll 1)$ es simular la operación de "carry-bit"). Me preguntaba "qué tan bien" funcionaba esta aproximación en términos de la distancia de Hamming entre $a+b$ y $a \oplus b \oplus ((a \land b) \ll 1).$

Vamos a ser precisos.

Versión formal. Sea $\{0,1\}^\mathbb{N}$ el conjunto de funciones $f:\mathbb{N}\to \{0,1\}$ y sea $$\{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))\}.$$ Cada miembro de $\{0,1\}^*$ puede ser visto como la expansión binaria de un número natural; esta es una correspondencia única. Esta correspondencia da lugar a la adición $+:\{0,1\}^* \times \{0,1\}^* \to \{0,1\}^*$. Denotamos por $\ll 1$ el corrimiento a la izquierda en una posición, es decir, $\ll 1 : x \in \{0,1\}^* \to x'\in \{0,1\}^*$ donde $x'(0) = 0$ y $x'(n+1) = x(n)$ para todo $n\in \mathbb{N}$. Por lo general, escribimos $x \ll 1$ en lugar de $\ll 1(x)$.

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

Para $a,b\in\mathbb{N}$ denotamos por $\text{diff}(a,b)$ la _distancia de Hamming_ entre $a+b$ y $a \oplus b \oplus ((a \land b) \ll 1)$.

Pregunta. ¿Tenemos $\max\{\text{diff}(a,b): a,b\in \{0,1\}^*\} < \infty$? Si no es así, ¿cuál es $\lim \sup_{n\to\infty} D_n$ donde $$D_n=\frac{1}{n} \max\{\text{diff}(a,b): a,b\in\{0,1\}^*, \max\{\text{len}(a),\text{len}(b)\} = n\}$$ para $n\geq 1$?

Answer 1

El límite superior es exactamente $1$. Casi con certeza, el valor exacto de $D_n$ proviene de $a = (1,1,1,\ldots,1)$ y $b = (1,0,0,\ldots,0)$, y aunque no lo sea, está como máximo a $O(1/n)$ de distancia, lo cual es inconsecuente. En este caso, tenemos aproximadamente el número máximo de acarreos que no son detectados por el $a \land b$. Entonces $a+b = 2^n$ pero $(a \land b) \ll 1 = 2$, por lo que la suma aproximada es $(0,0,1,1,1,\ldots,1)$, haciendo que la distancia de Hamming sea igual a $n-1$ (hay $n+1$ bits en $a+b$ y solo los dos más bajos coinciden). Por lo tanto, $D_n \ge 1 - \frac1n$.

Actualización: gracias a la observación del usuario44191, esta cota es de hecho precisa, por lo que $D_n = 1 - \frac1n$.