กลับไปหน้าบทความ

อ่าน 11 นาที

การดำเนินการบิต

เปลี่ยนทางจากคำนาม/เปลี่ยนเส้นทางไปยังส่วนต่างๆ

ในการเขียนโปรแกรมคอมพิวเตอร์ การดำเนินการแบบ บิตไวส์จะกระทำกับสตริงบิตอาร์เรย์บิตหรือตัวเลขไบนารี (ซึ่งถือว่าเป็นสตริงบิต) ในระดับบิต แต่ละบิต การดำเนินการนี้รวดเร็วและง่ายดาย

การดำเนินการบิต

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

โดยทั่วไปแล้ว ในโปรเซสเซอร์ราคาประหยัดแบบง่ายๆ การดำเนินการแบบบิตไวส์จะเร็วกว่าการหารอย่างมาก เร็วกว่าการคูณหลายเท่า และบางครั้งก็เร็วกว่าการบวกอย่างมีนัยสำคัญ ในขณะที่โปรเซสเซอร์สมัยใหม่มักจะทำการบวกและการคูณได้เร็วเท่ากับการดำเนินการแบบบิตไวส์ เนื่องจากมีไปป์ไลน์คำสั่ง ที่ยาวกว่า และ ตัวเลือกการออกแบบ ทางสถาปัตยกรรม อื่นๆ แต่การดำเนินการแบบบิตไวส์มักใช้พลังงานน้อยกว่าเนื่องจากการใช้ทรัพยากรที่ลดลง[ 1 ]

ตัวดำเนินการบิต

ในคำอธิบายด้านล่างนี้ การระบุตำแหน่งของบิตจะนับจากด้านขวา (ด้านที่มีค่าน้อยที่สุด) แล้วเลื่อนไปทางซ้าย ตัวอย่างเช่น ค่าไบนารี 0001 (เลขฐานสิบ 1) จะมีเลขศูนย์อยู่ทุกตำแหน่ง ยกเว้นตำแหน่งแรก (คือตำแหน่งขวาสุด)

ไม่

ตัว ดำเนินการ NOT ระดับบิตหรือตัวดำเนินการส่วนเติมเต็มระดับบิตเป็นการดำเนิน การทางตรรกะ แบบเอกภาค ที่ทำการ ปฏิเสธทางตรรกะในแต่ละบิต เพื่อสร้างส่วนเติมเต็มหนึ่ง (ones' complement)ของค่าไบนารีที่กำหนด บิตที่เป็น 0 จะกลายเป็น 1 และบิตที่เป็น 1 จะกลายเป็น 0 ตัวอย่างเช่น:

ไม่ใช่0 111 (เลขฐานสิบ 7) = 1,000 (เลขฐานสิบ 8)
ไม่ใช่ 10101011 (เลขฐานสิบ 171) = 01010100 (เลขฐานสิบ 84)

ผลลัพธ์จะเท่ากับ ค่า สองส่วนเติมเต็มลบหนึ่ง ถ้าใช้เลขคณิตแบบสองส่วนเติมเต็มแล้วจะได้NOT x = -x − 1.

สำหรับจำนวนเต็มที่ ไม่ติดลบ ค่าผกผันบิตของจำนวนนั้นคือ "ภาพสะท้อน" ของจำนวนนั้นที่จุดกึ่งกลางของช่วงของจำนวนเต็มที่ไม่ติดลบ ตัวอย่างเช่น สำหรับจำนวนเต็มที่ไม่ติดลบ 8 บิตNOT x = 255 - xซึ่งสามารถมองเห็นได้บนกราฟเป็นเส้นตรงที่ลากลง ซึ่ง "พลิก" ช่วงที่เพิ่มขึ้นจาก 0 ถึง 255 ไปเป็นช่วงที่ลดลงจาก 255 ถึง 0 ตัวอย่างการใช้งานที่ง่ายแต่ชัดเจนคือการกลับภาพขาวดำโดยที่แต่ละพิกเซลถูกจัดเก็บเป็นจำนวนเต็มที่ไม่ติดลบ

และ

การดำเนินการ AND แบบบิตของจำนวนเต็ม4 บิต

การ ดำเนินการ AND ระดับบิตเป็นการดำเนินการทางตรรกะแบบไบนารีที่รับเอาการแสดงค่าไบนารีสองค่าที่มีความยาวเท่ากัน และทำการ ดำเนินการ AND ระดับบิตกับแต่ละคู่ของบิตที่สอดคล้องกัน ดังนั้น หากบิตทั้งสองในตำแหน่งที่เปรียบเทียบเป็น 1 บิตในการแสดงค่าไบนารีที่ได้จะเป็น 1 (1  × 1  = 1) มิเช่นนั้น ผลลัพธ์จะเป็น 0 (1  × 0  = 0 และ 0  × 0  = 0) ตัวอย่างเช่น:

 010 1 (เลขฐานสิบ 5) และ 001 1 (เลขฐานสิบ 3) = 000 1 (เลขฐานสิบ 1)

การดำเนินการนี้อาจใช้เพื่อตรวจสอบว่าบิตใดบิตหนึ่งถูกตั้งค่า (1) หรือถูกล้าง (0) หรือไม่ ตัวอย่างเช่น เมื่อกำหนดรูปแบบบิต 0011 (เลขฐานสิบ 3) เพื่อตรวจสอบว่าบิตที่สองถูกตั้งค่าหรือไม่ เราจะใช้การดำเนินการ AND แบบบิตกับรูปแบบบิตที่มีค่า 1 เฉพาะในบิตที่สองเท่านั้น:

 00 1 1 (เลขฐานสิบ 3) และ 00 1 0 (เลขฐานสิบ 2) = 00 1 0 (เลขฐานสิบ 2)

เนื่องจากผลลัพธ์ 0010 ไม่ใช่ศูนย์ เราจึงทราบว่าบิตที่สองในรูปแบบเดิมถูกตั้งค่าไว้ ซึ่งมักเรียกว่าการมาสก์บิต (เปรียบเทียบกับการใช้เทปกาวปิดบังส่วน ที่ไม่ควร เปลี่ยนแปลงหรือส่วนที่ไม่เกี่ยวข้อง ในกรณีนี้ ค่า 0 จะมาสก์บิตที่ไม่เกี่ยวข้อง)

ตัวดำเนินการ AND ระดับบิตสามารถใช้เพื่อล้างบิต (หรือแฟล็ก ) ที่เลือกไว้ในรีจิสเตอร์ซึ่งแต่ละบิตแทนสถานะบูลีน แต่ละ ค่า เทคนิคนี้เป็นวิธีที่มีประสิทธิภาพในการจัดเก็บค่าบูลีนจำนวนมากโดยใช้หน่วยความจำให้น้อยที่สุด

ตัวอย่างเช่น 0110 (เลขฐานสิบ 6) สามารถพิจารณาได้ว่าเป็นชุดของแฟล็กสี่ตัวที่เรียงลำดับจากขวาไปซ้าย โดยแฟล็กแรกและแฟล็กที่สี่เป็นค่าว่าง (0) และแฟล็กที่สองและแฟล็กที่สามเป็นค่าที่ตั้งไว้ (1) แฟล็กที่สามสามารถล้างค่าได้โดยใช้การดำเนินการ AND แบบบิตกับรูปแบบที่มีค่าศูนย์เฉพาะในบิตที่สามเท่านั้น:

 0 1 10 (เลขฐานสิบ 6) และ 1 0 11 (เลขฐานสิบ 11) = 0 0 10 (เลขฐานสิบ 2)

เนื่องจากคุณสมบัตินี้ จึงทำให้สามารถตรวจสอบสถานะคู่/คี่ของเลขฐานสองได้ง่ายๆ โดยการตรวจสอบค่าของบิตที่มีค่าน้อยที่สุด โดยใช้ตัวอย่างข้างต้น:

 011 0 (เลขฐานสิบ 6) และ 000 1 (เลขฐานสิบ 1) = 000 0 (เลขฐานสิบ 0)

เนื่องจาก 6 และ 1 รวมกันได้ศูนย์ ดังนั้น 6 จึงหารด้วย 2 ลงตัว และจึงเป็นจำนวนคู่

หรือ

การดำเนินการ OR แบบบิตของจำนวนเต็ม 4 บิต

การ ดำเนินการ OR ระดับบิตเป็นการดำเนินการไบนารีที่รับรูปแบบบิตสองรูปแบบที่มีความยาวเท่ากัน และทำการ ดำเนินการ OR แบบรวมทางตรรกะกับแต่ละคู่ของบิตที่สอดคล้องกัน ผลลัพธ์ในแต่ละตำแหน่งจะเป็น 0 ถ้าทั้งสองบิตเป็น 0 ในขณะที่ถ้าเป็นอย่างอื่น ผลลัพธ์จะเป็น 1 ตัวอย่างเช่น:

 0 101 (เลขฐานสิบ 5) หรือ 0 011 (เลขฐานสิบ 3) = 0 111 (เลขฐานสิบ 7)

สามารถใช้การดำเนินการ OR แบบบิตเพื่อตั้งค่าบิตที่เลือกในรีจิสเตอร์ที่อธิบายไว้ข้างต้นให้เป็น 1 ได้ ตัวอย่างเช่น บิตที่สี่ของ 0010 (เลขฐานสิบ 2) สามารถตั้งค่าได้โดยการดำเนินการ OR แบบบิตกับรูปแบบที่มีการตั้งค่าเฉพาะบิตที่สี่เท่านั้น:

0 0 1 0 (เลขฐานสิบ 2) หรือ1 0 0 0 (เลขฐานสิบ 8) = 1 0 1 0 (เลขฐานสิบ 10)

เอ็กซ์ออร์

การดำเนินการ XOR ระดับบิตของจำนวนเต็ม 4 บิต

การ ดำเนินการ XOR ระดับบิตเป็นการดำเนินการไบนารีที่รับรูปแบบบิตสองรูปแบบที่มีความยาวเท่ากัน และทำการ ดำเนินการ XOR ทางตรรกะกับบิตแต่ละคู่ที่สอดคล้องกัน ผลลัพธ์ในแต่ละตำแหน่งจะเป็น 1 ถ้ามีเพียงบิตเดียวที่เป็น 1 แต่จะเป็น 0 ถ้าทั้งสองบิตเป็น 0 หรือทั้งสองบิตเป็น 1 ในการดำเนินการนี้ เราจะทำการเปรียบเทียบสองบิต โดยจะได้ค่า 1 ถ้าสองบิตนั้นแตกต่างกัน และ 0 ถ้าสองบิตนั้นเหมือนกัน ตัวอย่างเช่น:

 0 10 1 (เลขฐานสิบ 5) XOR 0 01 1 (เลขฐานสิบ 3) = 0 11 0 (เลขฐานสิบ 6)

การดำเนินการ XOR ระดับบิตสามารถใช้เพื่อกลับค่าบิตที่เลือกในรีจิสเตอร์ (เรียกอีกอย่างว่าการสลับหรือการพลิก) สามารถสลับค่าบิตใดก็ได้โดยการ XOR กับ 1 ตัวอย่างเช่น หากรูปแบบบิตเป็น 0010 (เลขฐานสิบ 2) บิตที่สองและสี่สามารถสลับค่าได้โดยการ XOR ระดับบิตกับรูปแบบบิตที่มีค่า 1 ในตำแหน่งที่สองและสี่:

0 0 1 0 (เลขฐานสิบ 2) XOR 1 0 1 0 (เลขฐานสิบ 10) = 1 0 0 0 (เลขฐานสิบ 8)

เทคนิคนี้อาจใช้เพื่อจัดการรูปแบบบิตที่แสดงถึงชุดสถานะบูลีน

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

หาก เรามองว่าเซตของสตริงบิตที่มีความยาวคงที่n (เช่นคำของเครื่อง ) เป็น ปริภูมิเวกเตอร์nมิติเอฟ2n{\displaystyle {\bf {F}}_{2}^{n}}ข้ามสนามเอฟ2{\displaystyle {\bf {F}}_{2}}ดังนั้น การบวกเวกเตอร์จึงสอดคล้องกับการดำเนินการ XOR ระดับบิต

ค่าเทียบเท่าทางคณิตศาสตร์

สมมติว่าxy{\displaystyle x\geq y}สำหรับจำนวน เต็มที่ไม่เป็นลบ การดำเนินการแบบบิตไวส์สามารถเขียนได้ดังนี้:

ไม่(x)=n=0บันทึก2x2n((x2nม็อด2+1)ม็อด2)=(2บันทึก2x+11)xxและy=n=0บันทึก2x2n(x2nม็อด2)(y2nม็อด2)xหรือy=n=0บันทึก2x2n(x2nม็อด2+y2nม็อด2(x2nม็อด2)(y2nม็อด2))xเอ็กซ์ออร์y=n=0บันทึก2x2n((x2n+y2n)ม็อด2){\displaystyle {\begin{aligned}\operatorname {NOT} (x)&=\sum _{n=0}^{\lfloor \log _{2}x\rfloor }2^{n}\left(\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+1\right){\bmod {2}}\right)\\&=\left(2^{\lfloor \log _{2}x\rfloor +1}-1\right)-x\\[10pt]x\operatorname {AND} y&=\sum _{n=0}^{\lfloor \log _{2}x\rfloor }2^{n}\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\\[10pt]x\operatorname {OR} y&=\sum _{n=0}^{\lfloor \log _{2}x\rfloor }2^{n}{\Bigg (}\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\\&\qquad \qquad -\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right){\Bigg )}\\[10pt]x\operatorname {XOR} y&=\sum _{n=0}^{\lfloor \log _{2}x\rfloor }2^{n}\left(\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor +\left\lfloor {\frac {y}{2^{n}}}\right\rfloor \right){\bmod {2}}\right)\end{aligned}}}

ตารางความจริงสำหรับตัวดำเนินการตรรกะไบนารีทั้งหมด

มีฟังก์ชันความจริง ที่เป็นไปได้ 16 แบบ สำหรับตัวแปรไบนารี สองตัว ซึ่งกำหนดตารางความจริง เรียกว่า ตารางค้นหา LUT2 หรือเรียกอีกอย่างว่าฟังก์ชันบูลีนลำดับ k =2 (อินพุต 2 ตัว) ผู้ผลิตบางรายใช้คำว่าconnective [ 2 ]สำหรับคำสั่งที่มีฟิลด์ 4 บิตที่ระบุตัวเชื่อมต่อไบนารีเฉพาะ ผู้ผลิตบางรายใช้คำว่าการดำเนินการบูลีน[ 3 ]สำหรับรหัสคำสั่งที่แตกต่างกัน 16 แบบ

ต่อไปนี้คือการดำเนินการเทียบเท่าระดับบิตของบิตสองบิต P และ Q:

พีqเอฟ0นอร์1Xq 2¬p 34¬q 5XOR 6เอ็นแอนด์7และ8เอ็กซ์นอร์9q 10ถ้า/แล้ว11หน้า12แล้ว/ถ้า13หรือ14ที15
110000000011111111
100000111100001111
010011001100110011
000101010101010101
ค่าเทียบเท่าบิต0ไม่ใช่(p หรือ q)(ไม่ใช่ p) และ qไม่ใช่pp และ(ไม่ใช่ q)ไม่ใช่qp XOR qไม่ใช่(p และ q)p และ qไม่ใช่(p XOR q)q(ไม่ใช่ p) หรือ qพีp หรือ(ไม่ใช่ q)พี หรือ คิว1

ค่าเทียบเท่าของเลขฐานสามคือฟังก์ชันบูลีน LUT3 อันดับ k=3 (อินพุตสามตัว) ซึ่งส่งผลให้ได้ตารางการดำเนินการ 256 รายการ และในทางคอมพิวเตอร์เรียกว่าคำสั่งตรรกะเลขฐานสามแบบบิต (Bitwise ternary logic instruction )

การเลื่อนบิต

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

การกำหนดแอดเดรสบิต

ถ้าความกว้างของรีจิสเตอร์ (โดยทั่วไปคือ 32 หรือแม้แต่ 64) มากกว่าจำนวนบิต (โดยปกติคือ 8) ของหน่วยที่เล็กที่สุดที่สามารถระบุตำแหน่งได้ ซึ่งมักเรียกว่าไบต์ การดำเนินการเลื่อนบิตจะเหนี่ยวนำให้เกิดรูปแบบการระบุตำแหน่งจากไบต์ไปเป็นบิต โดยที่ทิศทาง "ซ้าย" และ "ขวา" มาจากการเขียนตัวเลขมาตรฐานในระบบเลขฐานค่าประจำหลักกล่าวคือ การเลื่อนบิตไปทางซ้ายจะเพิ่มค่า และการเลื่อนบิตไปทางขวาจะลดค่าของตัวเลข ― ถ้าอ่านตัวเลขทางซ้ายก่อน จะทำให้เกิด การจัดเรียง แบบบิ๊กเอนเดียนโดยไม่คำนึงถึงผลกระทบที่ขอบเขตทั้งสองด้านของรีจิสเตอร์ การดำเนินการเลื่อนบิตทางคณิตศาสตร์และตรรกะจะทำงานเหมือนกัน และการเลื่อน บิต 8 ตำแหน่งจะเคลื่อนย้ายรูปแบบบิตไป 1  ตำแหน่งไบต์ในลักษณะต่อไปนี้:

การเรียงลำดับแบบ Little-endian :การเลื่อนไปทางซ้าย 8 ตำแหน่ง จะเพิ่มที่อยู่ไบต์ขึ้น 1 ตำแหน่ง
การเลื่อนบิตไปทางขวา 8 ตำแหน่ง จะทำให้แอดเดรสไบต์ลดลง 1 ตำแหน่ง
การเรียงลำดับ แบบบิ๊กเอนเดียน :การเลื่อนไปทางซ้าย 8 ตำแหน่ง จะทำให้แอดเดรสไบต์ลดลง 1 ตำแหน่ง
การเลื่อนบิตไปทางขวา 8 ตำแหน่ง จะเพิ่มที่อยู่ไบต์ขึ้น 1 ตำแหน่ง

การเลื่อนเลขคณิต

การเลื่อนเลขคณิตซ้าย
การเลื่อนเลขคณิตไปทางขวา

ในการเลื่อนบิตแบบเลขคณิต (sticky shift) บิตที่ถูกเลื่อนออกไปจากปลายทั้งสองข้างจะถูกทิ้งไป ในการเลื่อนบิตแบบเลขคณิตซ้าย บิตศูนย์จะถูกเลื่อนเข้ามาทางด้านขวา ในการเลื่อนบิตแบบเลขคณิตขวาบิตเครื่องหมาย (บิตที่มี ค่ามากที่สุด (MSB) ในระบบเลขสองคอมพลีเมนต์) จะถูกเลื่อนเข้ามาทางด้านซ้าย ทำให้รักษาเครื่องหมายของตัวถูกดำเนินการไว้

ตัวอย่างนี้ใช้รีจิสเตอร์ 8 บิต ซึ่งถูกตีความว่าเป็นค่าสองคอมพลีเมนต์:

 00010111 (เลขฐานสิบ +23) เลื่อนซ้าย = 0010111 0 (เลขฐานสิบ +46)
 10010111 (เลขฐานสิบ −105) เลื่อนขวา = 1 1001011 (เลขฐานสิบ −53)

ในกรณีแรก ตัวเลขหลักซ้ายสุดถูกเลื่อนเลยจุดสิ้นสุดของรีจิสเตอร์ และเลข 0 ใหม่ถูกเลื่อนเข้าไปในตำแหน่งขวาสุด ในกรณีที่สอง เลข 1 หลักขวาสุดถูกเลื่อนออกไป (อาจจะไปอยู่ในช่องทดเลข ) และเลข 1 ใหม่ถูกคัดลอกเข้าไปในตำแหน่งซ้ายสุด โดยคงเครื่องหมายของตัวเลขไว้ การเลื่อนหลายครั้งอาจถูกย่อให้เหลือการเลื่อนเพียงครั้งเดียวตามจำนวนหลักที่กำหนด ตัวอย่างเช่น:

 00010111 (เลขฐานสิบ +23) เลื่อนซ้ายไปสอง = 010111 00 (เลขฐานสิบ +92)

การเลื่อนเลขคณิตไปทางซ้ายn ครั้งเทียบเท่ากับการคูณด้วย 2n (โดยที่ค่าไม่เกินขีดจำกัด ) ในขณะที่การเลื่อนเลขคณิตไปทางขวาn ครั้ง ของ ค่า เลขฐานสองแบบส่วนเติมเต็มสองเทียบเท่ากับการปัดเศษลงของหารด้วย2nหากเลขฐานสองนั้นถูกมองว่าเป็นแบบส่วนเติมเต็มหนึ่งการเลื่อนไปทางขวาแบบเดียวกันนี้จะส่งผลให้หารด้วย 2n และปัดเศษเข้าหาศูนย์

การเปลี่ยนแปลงเชิงตรรกะ

การเลื่อนตรรกะไปทางซ้าย
การเปลี่ยนตรรกะที่ถูกต้อง

ในการเลื่อนบิตแบบตรรกะ (การเลื่อนบิตเพื่อเติมศูนย์) จะมีการเลื่อนศูนย์เข้าไปแทนที่บิตที่ถูกทิ้งไป ดังนั้น การเลื่อนบิตซ้ายแบบตรรกะและการเลื่อนบิตซ้ายแบบเลขคณิตจึงเหมือนกันทุกประการ

อย่างไรก็ตาม เนื่องจากการเลื่อนบิตไปทางขวาเชิงตรรกะจะแทรกบิตค่า 0 เข้าไปในบิตที่มีค่ามากที่สุด แทนที่จะคัดลอกบิตเครื่องหมาย จึงเหมาะสำหรับเลขฐาน สองแบบไม่มีเครื่องหมาย ในขณะที่การเลื่อนบิตไปทางขวาเชิงเลขคณิตเหมาะสำหรับ เลขฐานสองแบบสองคอมพลีเมนต์ที่ มีเครื่องหมาย

การเลื่อนแบบวงกลม

การ เลื่อนบิตอีกรูปแบบหนึ่งคือ การเลื่อน แบบวงกลมหรือ การ หมุนบิต

หมุน

การเลื่อนหรือหมุนแบบวงกลมซ้าย
การเลื่อนหรือหมุนแบบวงกลมขวา

ในกระบวนการนี้ ซึ่งบางครั้งเรียกว่าการหมุนแบบไม่ทด (rotate no carry ) บิตจะถูก "หมุน" ราวกับว่าปลายด้านซ้ายและด้านขวาของรีจิสเตอร์ถูกต่อเข้าด้วยกัน ค่าที่ถูกเลื่อนเข้าไปทางขวาในระหว่างการเลื่อนซ้ายจะเป็นค่าเดียวกับที่ถูกเลื่อนออกไปทางซ้าย และในทางกลับกันสำหรับการเลื่อนขวา กระบวนการนี้มีประโยชน์หากจำเป็นต้องเก็บรักษาบิตที่มีอยู่ทั้งหมด และมักใช้ในด้านการเข้ารหัส แบบ ดิจิทัล

หมุนผ่านขณะถือ

หมุนซ้ายผ่านท่าแบกรับ
หมุนขวาผ่านท่าแบกรับ

การหมุนผ่านตัวทด (Rotate through carry)เป็นรูปแบบหนึ่งของการดำเนินการหมุน โดยบิตที่ถูกเลื่อนเข้ามา (ที่ปลายด้านใดด้านหนึ่ง) จะเป็นค่าเดิมของแฟล็กตัวทด และบิตที่ถูกเลื่อนออกไป (ที่ปลายอีกด้านหนึ่ง) จะกลายเป็นค่าใหม่ของแฟล็กตัวทด

คำ สั่ง rotate through carryเพียงครั้งเดียวสามารถจำลองการเลื่อนบิตแบบตรรกะหรือแบบเลขคณิตได้หนึ่งตำแหน่ง โดยการตั้งค่าแฟล็ก carry ไว้ล่วงหน้า ตัวอย่างเช่น ถ้าแฟล็ก carry มีค่าเป็น 0 จะx RIGHT-ROTATE-THROUGH-CARRY-BY-ONEเป็นการเลื่อนบิตไปทางขวาแบบตรรกะ และถ้าแฟล็ก carry มีค่าเป็นสำเนาของบิตเครื่องหมาย จะx RIGHT-ROTATE-THROUGH-CARRY-BY-ONEเป็นการเลื่อนบิตไปทางขวาแบบเลขคณิต ด้วยเหตุนี้ ไมโครคอนโทรลเลอร์บางตัว เช่นPIC รุ่นราคาประหยัด จึง มีเพียง คำสั่ง rotateและrotate through carry เท่านั้น และไม่มีคำสั่งการเลื่อนบิตแบบเลขคณิตหรือแบบตรรกะเพิ่มเติม

ฟังก์ชัน Rotate-through-carry มีประโยชน์อย่างยิ่งเมื่อทำการเลื่อนบิตในตัวเลขที่มีขนาดใหญ่กว่าขนาดเวิร์ด พื้นฐานของโปรเซสเซอร์ เนื่องจากหากตัวเลขขนาดใหญ่ถูกเก็บไว้ในรีจิสเตอร์สองตัว บิตที่ถูกเลื่อนออกจากปลายด้านหนึ่งของรีจิสเตอร์ตัวแรกจะต้องเข้ามาที่ปลายอีกด้านหนึ่งของรีจิสเตอร์ตัวที่สอง ด้วยฟังก์ชัน Rotate-through-carry บิตนั้นจะถูก "บันทึก" ไว้ในแฟล็ก carry ระหว่างการเลื่อนบิตครั้งแรก พร้อมที่จะเลื่อนเข้ามาในระหว่างการเลื่อนบิตครั้งที่สองโดยไม่ต้องมีการเตรียมการเพิ่มเติมใดๆ

ในภาษาระดับสูง

ในตระกูลภาษาซี

ในภาษา C และ C++ ตัวดำเนินการเลื่อนบิตเชิงตรรกะคือ " " สำหรับการเลื่อนไปทางซ้าย และ " " สำหรับการเลื่อนไปทางขวา จำนวนตำแหน่งที่จะเลื่อนจะระบุเป็นอาร์กิวเมนต์ตัวที่สองของตัวดำเนินการ ตัวอย่างเช่น<<>>

x = y << 2 ;

กำหนดxค่าผลลัพธ์ของการเลื่อนบิตyไปทางซ้ายสองบิต ซึ่งเทียบเท่ากับการคูณด้วยสี่

การเลื่อนบิตอาจส่งผลให้เกิดพฤติกรรมที่กำหนดโดยการใช้งานหรือพฤติกรรมที่ไม่กำหนดดังนั้นจึงต้องระมัดระวังเมื่อใช้งาน ผลลัพธ์ของการเลื่อนบิตด้วยจำนวนบิตที่มากกว่าหรือเท่ากับขนาดของคำถือเป็นพฤติกรรมที่ไม่กำหนดในภาษา C และ C++ [ 4 ] [ 5 ]การเลื่อนบิตไปทางขวาของค่าลบเป็นพฤติกรรมที่กำหนดโดยการใช้งานและไม่แนะนำตามหลักปฏิบัติการเขียนโค้ดที่ดี[ 6 ]ผลลัพธ์ของการเลื่อนบิตไปทางซ้ายของค่าที่มีเครื่องหมายถือเป็นพฤติกรรมที่ไม่กำหนดหากผลลัพธ์ไม่สามารถแสดงในประเภทผลลัพธ์ได้[ 4 ]

ใน C# การเลื่อนบิตไปทางขวาเป็นการเลื่อนบิตแบบเลขคณิตเมื่อตัวถูกดำเนินการตัวแรกเป็น int หรือ long หากตัวถูกดำเนินการตัวแรกเป็นประเภท uint หรือ ulong การเลื่อนบิตไปทางขวาจะเป็นการเลื่อนบิตแบบตรรกะ[ 7 ]

การเปลี่ยนแปลงแบบวงกลม

ภาษาตระกูล C ขาดตัวดำเนินการหมุน (แม้ว่า C++20 จะมีstd::rotlและstd::rotr) แต่สามารถสร้างตัวดำเนินการหมุนได้จากตัวดำเนินการเลื่อน ต้องระมัดระวังเพื่อให้แน่ใจว่าคำสั่งนั้นถูกต้องเพื่อหลีกเลี่ยงพฤติกรรมที่ไม่กำหนดและการโจมตีเวลาในซอฟต์แวร์ที่มีข้อกำหนดด้านความปลอดภัย[ 8 ]ตัวอย่างเช่น การใช้งานแบบง่ายๆ ที่หมุนค่าที่ไม่ระบุเครื่องหมาย 32 บิตไปทางซ้ายxตามnตำแหน่งนั้นทำได้ง่ายๆ

uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( 32 - n ));

อย่างไรก็ตาม การเลื่อน0บิตส่งผลให้เกิดพฤติกรรมที่ไม่แน่นอนในนิพจน์ด้านขวา(x >> (32 - n))เนื่องจาก32 - 0และอยู่นอกช่วง 0–31 รวมทั้งสองค่า การลองครั้งที่สองอาจส่งผลให้32เกิด32

uint32_t x = ..., n = ...; uint32_t y = n ? ( x << n ) | ( x >> ( 32 - n )) : x ;

โดยปริมาณการเลื่อนจะถูกทดสอบเพื่อให้แน่ใจว่าจะไม่ก่อให้เกิดพฤติกรรมที่ไม่กำหนดไว้ อย่างไรก็ตาม สาขาจะเพิ่มเส้นทางโค้ดเพิ่มเติมและเปิดโอกาสให้มีการวิเคราะห์เวลาและการโจมตี ซึ่งมักจะไม่เป็นที่ยอมรับในซอฟต์แวร์ที่มีความสมบูรณ์สูง[ 8 ]นอกจากนี้ โค้ดจะถูกคอมไพล์เป็นคำสั่งเครื่องหลายคำสั่ง ซึ่งมักจะมีประสิทธิภาพน้อยกว่าคำสั่งดั้งเดิมของโปรเซสเซอร์

เพื่อหลีกเลี่ยงพฤติกรรมที่ไม่แน่นอนและการแยกสาขาภายใต้GCCและClangขอแนะนำดังต่อไปนี้ รูปแบบนี้ได้รับการยอมรับจากคอมไพเลอร์หลายตัว และคอมไพเลอร์จะสร้างคำสั่งหมุนเพียงคำสั่งเดียว: [ 9 ] [ 10 ] [ 11 ]

uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( - n & 31 ));

นอกจากนี้ยังมีฟังก์ชัน เฉพาะคอมไพเลอร์ ที่ใช้การเลื่อนแบบวงกลมเช่น_rotl8, _rotl16 , _rotr8, _rotr16ใน Microsoft Visual C++ Clang มีฟังก์ชันการหมุนบางอย่างเพื่อความเข้ากันได้กับ Microsoft ซึ่งประสบปัญหาข้างต้น[ 11 ] GCC 15 ได้แนะนำ ฟังก์ชัน __builtin_stdc_rotate_leftและ__builtin_stdc_rotate_rightแต่ไม่สามารถเพิ่มประสิทธิภาพได้อย่างถูกต้อง Intel ยังมีฟังก์ชัน x86 อีกด้วย

ชวา

ในภาษา Javaชนิดข้อมูลจำนวนเต็มทั้งหมดเป็นแบบมีเครื่องหมาย ดังนั้นตัวดำเนินการ " " และ " " จึงทำการเลื่อนบิตทางเลขคณิต Java เพิ่มตัวดำเนินการ " " เพื่อทำการเลื่อนบิตไปทางขวาเชิงตรรกะ แต่เนื่องจากการเลื่อนบิตไปทางซ้ายเชิงตรรกะและทางเลขคณิตนั้นเหมือนกันสำหรับจำนวนเต็มแบบมีเครื่องหมาย จึงไม่มีตัวดำเนินการ " " ใน Java<<>>>>><<<

รายละเอียดเพิ่มเติมเกี่ยวกับตัวดำเนินการเลื่อนของ Java: [ 12 ]

  • ตัวดำเนินการ<<(เลื่อนซ้าย), >>(เลื่อนขวาแบบมีเครื่องหมาย) และ>>>(เลื่อนขวาแบบไม่มีเครื่องหมาย) เรียกว่าตัวดำเนินการเลื่อน (shift operators )
  • ชนิดของนิพจน์การเลื่อนบิตคือชนิดที่ถูกเลื่อนของตัวถูกดำเนินการทางซ้ายมือ ตัวอย่างเช่นaByte >>> 2เทียบเท่ากับ((int)aByte)>>>2
  • หากประเภทที่ส่งเสริมของตัวถูกดำเนินการด้านซ้ายเป็น int จะใช้บิตลำดับต่ำสุดห้าบิตของตัวถูกดำเนินการด้านขวาเป็นระยะการเลื่อนเท่านั้น เสมือนว่าตัวถูกดำเนินการด้านขวาถูกดำเนินการด้วยตัวดำเนินการ AND เชิงตรรกะแบบบิต & ด้วยค่ามาสก์ 0x1f (0b11111) [ 13 ]ดังนั้นระยะการเลื่อนที่ใช้จริงจึงอยู่ในช่วง 0 ถึง 31 รวมทั้งสองค่า
  • หากประเภทที่ส่งเสริมของตัวถูกดำเนินการด้านซ้ายยาว จะใช้บิตลำดับต่ำสุดหกบิตของตัวถูกดำเนินการด้านขวาเพียงระยะการเลื่อนเท่านั้น เสมือนว่าตัวถูกดำเนินการด้านขวาถูกดำเนินการด้วยตัวดำเนินการ AND ตรรกะแบบบิต & ด้วยค่ามาสก์ 0x3f (0b111111) [ 13 ]ดังนั้นระยะการเลื่อนที่ใช้จริงจึงอยู่ในช่วง 0 ถึง 63 รวมทั้งสองค่า
  • The value of n >>> s is n right-shifted s bit positions with zero-extension.
  • In bit and shift operations, the type byte is implicitly converted to int. If the byte value is negative, the highest bit is one, then ones are used to fill up the extra bytes in the int. So byteb1=-5;inti=b1|0x0200; will result in i == -5.

JavaScript

JavaScript uses bitwise operations to evaluate each of two or more units place to 1 or 0.[14]

Pascal

In Pascal, as well as in all its dialects (such as Object Pascal and Standard Pascal), the logical left and right shift operators are "shl" and "shr", respectively. Even for signed integers, shr behaves like a logical shift, and does not copy the sign bit. The number of places to shift is given as the second argument. For example, the following assigns x the result of shifting y to the left by two bits:

x:=yshl2;

Other

Applications

Bitwise operations are necessary particularly in lower-level programming such as device drivers, low-level graphics, communications protocol packet assembly, and decoding.

Although machines often have efficient built-in instructions for performing arithmetic and logical operations, all these operations can be performed by combining the bitwise operators and zero-testing in various ways.[15] For example, here is a pseudocode implementation of ancient Egyptian multiplication showing how to multiply two arbitrary integers a and b (a greater than b) using only bitshifts and addition:

c0whileb0if(band1)0cc+aleftshiftaby1rightshiftbby1returnc

Another example is a pseudocode implementation of addition, showing how to calculate a sum of two integers a and b using bitwise operators and zero-testing:

ในขณะที่a 0 c b และa b b xor a เลื่อนc ไปทางซ้าย1 ตำแหน่งa c คืนค่าb

พีชคณิตบูลีน

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

และ

  • x & y = y & x
  • x & (y & z) = (x & y) & z
  • x & 0xFFFF = x[ 16 ]
  • x & 0 = 0
  • x & x = x

หรือ

  • x | y = y | x
  • x | (y | z) = (x | y) | z
  • x | 0 = x
  • x | 0xFFFF = 0xFFFF
  • x | x = x

ไม่

  • ~(~x) = x

เอ็กซ์ออร์

  • x ^ y = y ^ x
  • x ^ (y ^ z) = (x ^ y) ^ z
  • x ^ 0 = x
  • x ^ y ^ y = x
  • x ^ x = 0
  • x ^ 0xFFFF = ~x

นอกจากนี้ XOR ยังสามารถประกอบขึ้นจากโอเปอเรชันพื้นฐาน 3 อย่าง (AND, OR, NOT) ได้อีกด้วย

  • a ^ b = (a | b) & (~a | ~b)
  • a ^ b = (a & ~b) | (~a & b)

คนอื่น

  • x | (x & y) = x
  • x & (x | y) = x
  • ~(x | y) = ~x & ~y
  • ~(x & y) = ~x | ~y
  • x | (y & z) = (x | y) & (x | z)
  • x & (y | z) = (x & y) | (x & z)
  • x & (y ^ z) = (x & y) ^ (x & z)
  • x + y = (x ^ y) + ((x & y) << 1)
  • x - y = ~(~x + y)

ตัวผกผันและการแก้สมการ

การหาค่าตัวแปรในพีชคณิตบูลีนอาจเป็นเรื่องยาก เพราะต่างจากพีชคณิตทั่วไป การดำเนินการหลายอย่างไม่มีตัวผกผัน การดำเนินการที่ไม่มีตัวผกผันจะทำให้ข้อมูลบางส่วนหายไป และไม่สามารถกู้คืนข้อมูลที่หายไปนี้ได้

  • มีสิ่งที่ตรงกันข้าม
    • ไม่
    • เอ็กซ์ออร์
    • หมุนไปทางซ้าย
    • หมุนไปทางขวา
  • ไม่มีสิ่งที่ตรงกันข้าม
    • และ
    • หรือ
    • เลื่อนไปทางซ้าย
    • เลื่อนไปทางขวา

ลำดับการดำเนินการ

การดำเนินการที่อยู่ด้านบนสุดของรายการนี้จะถูกดำเนินการก่อน ดูรายการที่ครบถ้วนยิ่งขึ้นได้ในบทความหลัก

ดูเพิ่มเติม

  • เครื่องคิดเลขบิตไวส์ออนไลน์รองรับการดำเนินการบิตไวส์ AND, OR และ XOR
  • XORcatเครื่องมือสำหรับประมวลผลไฟล์/สตรีมแบบ XOR บิต
  • การหารโดยใช้การเลื่อนบิต
  • " การดำเนินการบิตไวส์ Mod N " โดย Enrique Zeleny, โครงการสาธิต Wolfram
  • " แผนภาพแสดงการประกอบกันของการดำเนินการบิตไวส์ " โดย Enrique Zeleny จากโครงการ Wolfram Demonstrations Project
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Bitwise_operation&oldid=1361910524#Bit_shifts "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ การดำเนินการบิต

ในการเขียนโปรแกรมคอมพิวเตอร์ การดำเนินการแบบ บิตไวส์จะกระทำกับสตริงบิตอาร์เรย์บิตหรือตัวเลขไบนารี (ซึ่งถือว่าเป็นสตริงบิต) ในระดับบิต แต่ละบิต การดำเนินการนี้รวดเร็วและง่ายดาย

ตัวดำเนินการบิต

ในคำอธิบายด้านล่างนี้ การระบุตำแหน่งของบิตจะนับจากด้านขวา (ด้านที่มีค่าน้อยที่สุด) แล้วเลื่อนไปทางซ้าย ตัวอย่างเช่น ค่าไบนารี 0001 (เลขฐานสิบ 1) จะมีเลขศูนย์อยู่ทุกตำแหน่ง ยกเว้นตำแหน่งแรก (คือตำแหน่งขวาสุด)

ไม่

ตัว ดำเนินการ NOT ระดับบิต หรือ ตัวดำเนินการส่วนเติมเต็มระดับบิต เป็นการดำเนิน การทางตรรกะ แบบเอกภาค ที่ทำการ ปฏิเสธทางตรรกะ ในแต่ละบิต เพื่อสร้าง ส่วนเติมเต็มหนึ่ง (ones' complement) ของค่าไบนารีที่กำหนด บิตที่เป็น 0 จะกลายเป็น 1 และบิตที่เป็น 1 จะกลายเป็น 0...

และ

การ ดำเนินการ AND ระดับบิต เป็นการ ดำเนินการทางตรรกะแบบไบนารี ที่รับเอาการแสดงค่าไบนารีสองค่าที่มีความยาวเท่ากัน และทำการ ดำเนินการ AND ระดับบิต กับแต่ละคู่ของบิตที่สอดคล้องกัน ดังนั้น หากบิตทั้งสองในตำแหน่งที่เปรียบเทียบเป็น 1...