Universalità di $ (+, \ oplus) $ oltre $ \ mathbb {z} _2 ^ n $

Question

Let $ \ MATHBB {Z} _2 ^ N $ Sii il campo dei bitvectors di lunghezza $ N $ e definisci l'operatore XOR $ \ oplus $ e l'operatore di aggiunta $ + $ su questo campo, con $ + $ Avere la solita semantica di overflow (prendi l'aggiunta di Modulo $ 2 ^ N $ ). è possibile esprimere qualsiasi mappatura $ f: \ mathbb {z} _2 ^ n \ reapyarrow \ mathbb {z} _2 ^ n $ interamente in termini di $ \ Oplus $ e $ + $ ? Sembra che potrebbe essere possibile a causa della non linearità della $ + $ .

---

.

Ad esempio, se ci è stato dato $ n= 2 $ e quella $ f (0)= 3, f (1)= 1, F (2)= 3, f (3)= 1 $ , quindi potremmo costruire $ f $ come classe $ f (x)= x \ oplus (x + 3) $ .

Answer 1

no.Ad esempio, non è possibile esprimere la funzione $ f (x)= x >> 1 $ .In generale, il bit meno significativo di $ f (x) $ dipende solo dal bit meno significativo di $ x$ .Puoi dimostrarlo da induzione strutturale, utilizzando le seguenti due proprietà: $ (a \ oplus b) \ bmod 2= (a \ bmod 2) \ oplus (b \ bmod 2) $ e $ (A + B) \ BMOD 2= (A \ BMOD 2) + (B \ BMOD 2) \ BMOD 2 $ .