$ \ mathbb 이상의 $ (+, \ oplus) $의 보편성 {z} _2 ^ n $

Question

$ \ mathbb {z} _2 ^ n $ 길이 $ n $ 및 XOR 연산자 $ \ oplus $ 및 추가 연산자 $ + $ 을 정의합니다. $ + $ 보통 오버플로 의미 (추가 모듈로 $ 2 ^ n $ )를 가지고 있습니다. 는 매핑 $ f : \ mathbb {z} _2 ^ n \ Nowarrow \ mathbb {z} _2 ^ n $ 을 전적으로 표현할 수 있습니다. $ \ oplus $ 및 $ + $ ? $ + $ 의 비선형 성으로 인해 가능할 수도있는 것처럼 보입니다.

---

$ n= 2 $ 및 $ f (0)= 3, f (1)= 1, f (2)= 3, f (3)= 1 $ , $ f $ 을 $ f (x)= x \ oplus (x + 3) $

Answer 1

아니오.예를 들어 함수 $ f (x)= x >> 1 $ 을 표현할 수 없습니다.일반적으로 $ f (x) $ 의 최소한의 비트는 $ x의 최소 비트에만 의존합니다.$ . $ (a \ oplus b) \ bmod 2= (a \ bmod 2) \ oplus (b \ bmod 2) $ 및 $ (a + b) \ bmod 2= (a \ bmod 2) + (b \ bmod 2) \ bmod 2 $ .