# Inverses of the operation $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ for fixed bit length

Background. 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 \; \approx \; 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.)

Formulation of question. We can view this as an operation $$+^{n}_\sim : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}^n$$, defined by $$(a, b) \mapsto a \oplus b \oplus ((a \land b) \ll 1)$$. For $$b\in \{0,1\}^n$$ we get a map $$s^n_b: \{0,1\}^n\to \{0,1\}^n$$ defined by $$a \mapsto a +^{n}_\sim b.$$

Is $$s^n_b$$ injective (and therefore bijective) for all $$n\in\mathbb{N}$$ and $$b\in \{0,1\}^n$$?

• That's half-adder. To use it for n-bit you need Full-adder to propagate. Mar 15, 2022 at 12:42
• Is this a homework question? Mar 15, 2022 at 12:49
• Actually, the $s_b^n$ is not well defined. What does happen to the last carry? Mar 15, 2022 at 17:56

Yes, to see this note that $$a$$ can be computed bitwise from the least significant bit. We write $$c$$ for $$a+^n_\sim b$$ and $$x_i$$ for the $$i$$th bit of $$x$$. Observe that: $$a_0=b_0\oplus c_0$$ $$a_i=b_i\oplus c_i\oplus (a_{i-1}\wedge b_{i-1})$$ for $$1\le i\le n-1$$.
Sadly, there is not a nice 4-bit to 1 bit function bitwise inverse function $$(b,c)\mapsto a$$ e.g. $$a_2$$ is a function of $$b_0$$, $$b_1$$, $$b_2$$, $$c_0$$ and $$c_1$$.