การดำเนินการที่ไวต่อคำสั่งที่เร็วที่สุด

สำหรับใดๆ $v$ มากมาย $ข$-บิตเวกเตอร์ $(\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}) \in \{\{0, 1\}^b\}^v$,อะไรคือ เร็วที่สุด วิธีการรวม $\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}$ เป็นเลขตัวเดียว เช่น การดำเนินการนั้น สั่งไว?

เช่น. บอกว่า $\หมวก+$ เป็นวิธีการรวมตัวเลข (ไม่จำเป็นต้องบวก แต่เราสามารถกำหนดได้ตามที่เราต้องการ) เป้าหมายคือการมี $\mathbf{x}_0 \hat+ \mathbf{x}_1 \hat+ \ldots \hat+ \mathbf{x}_{v-1}$ ทำให้ได้หมายเลขเฉพาะที่แตกต่างจากคำสั่งอื่นๆ เช่น $\mathbf{x}_{v-1} \hat+ \mathbf{x}_{v-2} \hat+ \ldots \hat+ \mathbf{x}_0$.

ส่วน เร็วที่สุด, ความเร็วจะวัดจาก CPU ที่ใช้งานทั่วไป เช่น. x86-64.

ความคิดของฉันจนถึงตอนนี้คือ:

b_bits_variable xor = 0;
สำหรับ (i = 0; i < v; i++) {
  xor = xor ^ (xor + x_i);
}

ที่ไหน:

• b_bits_variable เป็นตัวแปรที่มีตรง $ข$ หลายบิต เช่น. ถ้า $b=16$แล้วเราอาจใช้ uint16_t ในโปรแกรมภาษาซี
• โวลต์ เป็น $v$ (ปริมาณของเวกเตอร์ตามคำถามข้างต้น)
• x_i เป็น $\mathbf{x}_i$ (เวกเตอร์ในหมู่ $v$ หลายตัวดังคำถามข้างต้น)
• ฉัน ++ $= ฉัน+1$.
• ^ เป็น XOR ที่ฉลาดระดับบิต
• + เป็นการบวกที่ใช้กันทั่วไปในภาษาโปรแกรม ซึ่งจะล้นถ้าตัวเลขมากกว่า $2^b - 1$. ฉัน คิด ล้นดังกล่าวเป็นพื้นโมดูโล $2^b$ ส่วนที่เพิ่มเข้าไป. เช่น. xor + x_i $=\text{xor} + \mathbf{x}_i \mod 2^b$.

นี่เป็นแนวคิดง่ายๆ

ฉันจะใช้ $x_i$ สำหรับเวกเตอร์ใน $d$ ขนาดและการใช้งาน $a_i$ สำหรับจำนวนเต็มที่เกี่ยวข้อง ใน $\{0,1,\ldots, 2^d-1\}$.

เรียงลำดับ $a_i$ ตั้งแต่เล็กไปจนถึงใหญ่ อนุญาต $r_i$ มียศเป็น $a_i$ ใช้อันดับจาก $\{0,1,\ldots,v-1\}$. ทำลายความสัมพันธ์ระหว่างการเรียงลำดับโดยพลการ

ตัวอย่าง: $(a_1,a_2,a_3)=(1,7,2)$ มีเวกเตอร์อันดับ $(r_1,r_2,r_3)=(0,2,1).$ มีสามรายการที่มีหมายเลขตั้งแต่ 0 ถึง 2 และรายการตรงกลางคือ 7 ซึ่งใหญ่ที่สุดในอันดับที่ 2

ตอนนี้ให้พิจารณารายการการเรียงสับเปลี่ยนของวัตถุ 3 รายการตามลำดับศัพท์มาตรฐานและดัชนี

$$ 012~~0\\ 021~~1\\ 102~~2\\ 120~~3\\ 201~~4\\ 210~~5\\ $$ และโปรดทราบว่าการเรียงสับเปลี่ยนนี้คือ 021 ดังนั้นจึงมีตำแหน่ง 1 ในรายการการเรียงสับเปลี่ยน การเข้ารหัสตำแหน่งเป็นเวกเตอร์ไบนารีใช้เวลา $r=\lceil \log_2 v\rceil$ บิต

ถ้า $r\leq ง,$ เราสามารถกำหนดได้ $$ x_1+x_2+\cdots+x_v=x_1\oplus x_2\oplus \cdots\oplus x_v \oplus ดัชนี(การเรียงสับเปลี่ยน (x_1,\ldots,x_v)), $$ ดังนั้นในตอนท้ายเราจะ xor ดัชนีของการเรียงสับเปลี่ยนซึ่งเปลี่ยนแปลงถ้า $x_i$ มีการจัดลำดับใหม่