Score:1

ผกผันของการดำเนินการ $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ สำหรับความยาวบิตคงที่

ธง br

พื้นหลัง. ในพวกเขา กระดาษ เกี่ยวกับโครงร่างการเข้ารหัส NORX ผู้เขียนใช้การประมาณ + โดยการดำเนินการระดับบิตอย่างรวดเร็ว (ใช้รอบ CPU น้อยกว่าการเพิ่มที่เหมาะสม) โดยใช้สูตร $$a+b \; \ ประมาณ \; ก \oplus b \oplus ((a \land b) \ll 1)$$ ที่ไหน $\oบวก$ เป็น XOR ระดับบิตและ $\ที่ดิน$ เป็นระดับบิต AND และ $\ll$ เลื่อนไปทางซ้าย 1 ตำแหน่ง (จุดประสงค์ของ $((a \land b) \ll 1)$ คือการจำลองการทำงานของ "carry-bit")

การกำหนดคำถาม เราสามารถมองว่านี่เป็นการดำเนินการ $+^{n}_\sim : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}^n$, ที่กำหนดโดย $(a, b) \mapsto a \oplus b \oplus ((a \ที่ดิน ข) \ll 1)$. สำหรับ $b\in \{0,1\}^n$ เราได้แผนที่ $s^n_b: \{0,1\}^n\ถึง \{0,1\}^n$ ที่กำหนดโดย $$a \mapsto a +^{n}_\sim b.$$

เป็น $s^n_b$ ฉีด (และดังนั้น bijective) สำหรับทุกคน $n\in\mathbb{N}$ และ $b\in \{0,1\}^n$?

kelalaka avatar
in flag
นั่นคือครึ่งบวก หากต้องการใช้สำหรับ n-bit คุณต้องใช้ Full-adder เพื่อเผยแพร่
poncho avatar
my flag
นี่เป็นคำถามการบ้านหรือไม่?
kelalaka avatar
in flag
จริงๆ แล้ว $s_b^n$ นั้นไม่ได้ถูกนิยามไว้อย่างดี เกิดอะไรขึ้นกับการพกพาครั้งสุดท้าย?
Score:2
ธง ru

ใช่เพื่อดูบันทึกนี้ว่า $a$ สามารถคำนวณระดับบิตจากบิตที่มีนัยสำคัญน้อยที่สุด พวกเราเขียน $ค$ สำหรับ $a+^n_\ซิม b$ และ $x_i$ สำหรับ $i$บิตของ $x$. สังเกตว่า: $$a_0=b_0\oบวก c_0$$ $$a_i=b_i\oplus c_i\oplus (a_{i-1}\wedge b_{i-1})$$ สำหรับ $1\le ฉัน\le n-1$.

น่าเศร้าที่ไม่มีฟังก์ชั่นผกผัน 4 บิตถึง 1 บิตที่ดี $(b,c)\mapsto a$ เช่น. $a_2$ เป็นหน้าที่ของ $b_0$, $b_1$, $b_2$, $c_0$ และ $c_1$.

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา