When dealing with some hash functions that I was trying to speed up, I [toyed](https://mathoverflow.net/questions/394296/hamming-distance-between-ab-and-a-oplus-b-oplus-a-land-b-ll-1) with a binary operation with the goal to "approximate" the addition on $\{0,1\}^\*$ when seen as binary representation of the positive integers:


$$(a,b) \in (\{0,1\}^\*)^2 \mapsto 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.)


**Formal definition.** 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))\}.$$
Denote by $\ll 1$ the *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 any $a,b\in\{0,1\}^\*$ let us write $$a +\_2 b := a \oplus b \oplus ((a\land b) \ll 1).$$


It is easily seen that $+\_2$ is not associative, and that $0$ is a neutral element for every $x\in \{0,1\}^\*$. Moreover, $+\_2$ is clearly commutative


**Question.** Given $a,b\in \{0,1\}^\*$, is there $x\in \{0,1\}^\*$ such that $a +\_2 x = b$? Is $x$ necessarily unique?


**Further question.** (Need not be answered for acceptance.) If the answer to the above question is positive, we would have a kind of "non-associative group". Do these have a proper name? Do they occur "naturally" somewhere in mathematics?



Non-associative commutative "group"
The answer to the first question is **yes**:



> 
> **Claim.** Let $a, b \in \{0, 1 \}^{\ast}$ and let $n \ge 0$ be the least integer such that $a(i) = b(i) = 0$ for every $i > n$. Then the equation $$a +\_2 x = b$$ has a unique solution $x \in \{0, 1 \}^{\ast}$ which is recursively defined by $x(0) = a(0) + b(0)$, $x(i) = a(i - 1)x(i - 1) + a(i) + b(i)$ for $0 < i \le n$ and
> $x(n + 1) = a(n)x(n)$, $x(i) = 0$ for $i > n + 1$.
> Equivalently, the solution $x$ is given by  
> 
> $$
> \begin{array}{lll}
> x(0) &=& a(0) + b(0), \\
> x(1) &=& a(0)(a(0) + b(0)) + a(1) + b(1),\\
> ... & = & ..., \\
> x(n) & = & a(0) \cdots a(n - 1)(a(0) + b(0)) + a(1) \cdots a(n - 1)(a(1) + b(1)) + \cdots + a(n - 1)(a(n - 1) + b(n - 1)) + a(n) + b(n),
> \end{array}$$
> $x(n + 1) = a(n)x(n)$
> and $x(i) = 0$ for $n > n + 1$ where the operations $+$ and $\cdot$ refer to addition and multiplication in $\mathbb{Z} / 2 \mathbb{Z}$ which we identified with $\{0, 1 \}$.
> 
> 
> 



> 
> *Proof.* The equation is equivalent to $x \oplus ((a \wedge x) \ll 1) = a \oplus b$ which reads as a linear system over $\mathbb{Z} / 2 \mathbb{Z}$.
> 
> 
> 


