1
$\begingroup$

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$?

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

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.