/ 365วันแห่งโปรแกรม

[365 วันแห่งโปรแกรม #day35] Bitwise operations

วันที่สามสิบห้าของ ‪#‎365วันแห่งโปรแกรม วันนี้เราจะคุยกันเรื่อง Bitwise operations


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

ในทางโปรแกรมมิ่งในปัจจุบันแล้วเราเข้าใจตรงกันว่า เมื่อมีบิต 8 อันรวมกันเราจะเรียกมันว่า BYTE (ในทาง physical 8 bits อาจจะไม่เท่ากับ 1 byte เช่นบนแรมบางชนิด ใช้ 9 bits = 1 byte หรือ 12 bit = 1 byte) ถ้ามี 16 บิต ให้เรียกว่า WORD หรือถ้ามี 2 WORDs ก็จะเรียกว่า DWORD (32 บิต)

Bitwise operations ที่เป็นหัวข้อของเราในวันนี้ก็คือการทำงานกับบิตหรือกลุ่มของบิต (BYTE, WORD, DWORD) นั่นเอง ซึ่งในเมื่อบิตมีค่าแค่ 0 หรือ 1 การดำเนินการที่ทำได้ก็มีแต่การดำเนินการแบบตรรกศาสตร์ และการเลื่อนบิตไปมา การกระทำใดๆ ที่เกี่ยวกับบิตนั้นเราจำเป็นต้องใช้สิ่งที่เรียกว่า Bitwise operator หรือตัวนำเนินการแบบบิต

ตัวดำเนินการแบบบิต มีอยู่ 6 ตัว ดังนี้

1. & 	bitwise AND

2. | 	bitwise inclusive OR

3. ^ 	bitwise XOR

4. << 	left shift

5. >> 	right shift

6. ~ 	bitwise NOT

bitwise AND

bitwise AND มักถูกแทนด้วยเครื่องหมาย ampersand (&) ซึ่งจริงๆ แล้วก็คือสิ่งเดียวกันกับ AND ในตรรกศาสตร์ การจะใช้ bitwise AND นี้จำเป็นต้องมี operand (ตัวถูกดำเนินการ) 2 ตัว การทำงานจะเป็นการเทียบกันทีละบิตถ้าบิตในลำดับไหนมีค่าเป็น 1 เหมือนกันทั้งสองตัว (operand) ก็จะคืนค่า 1 ในตำแหน่งนั้น กรณีอื่นจะคืนค่าเป็น 0 ทั้งหมด

|------|------|------|
|   A  |   B  | A & B|
|------|------|------|
|   1  |   1  |   1  |
|   1  |   0  |   0  |
|   0  |   1  |   0  |
|   0  |   0  |   0  |
|------|------|------|

ตัวอย่างการใช้ bitwise AND ระหว่าง 16 และ 48 ซึ่งเป็นจำนวนเต็มขนาด 8 บิต

0 0 0 1 0 0 0 0  = 16
0 0 1 1 0 0 0 0  = 48
---------------  AND
0 0 0 1 0 0 0 0  = 16
= = = = = = = = 

จากตัวอย่างจะเห็นว่า 16 และ 48 มีบิตที่เป็น 1 ร่วมกันตำแหน่งเดียวคือบิตที่ 4 นับจากซ้ายมือ ดังนั้น ค่าที่ได้คือ 16

bitwise inclusive OR

bitwise inclusive OR ปกติจะแทนด้วยเครื่องหมาย pipe (|) เป็นตัวดำเนินการทางตรรกศาสตร์เช่นเดียวกับ AND และต้องการ operand 2 ตัวเช่นกัน ความต่างอยู่ที่ OR จะคืนค่าเป็น 1 ทุกกรณี เว้นแต่ว่าตำแหน่งนั้นมีค่าเป็น 0 ในทั้ง 2 operand

|------|------|------|
|   A  |   B  | A | B|
|------|------|------|
|   1  |   1  |   1  |
|   1  |   0  |   1  |
|   0  |   1  |   1  |
|   0  |   0  |   0  |
|------|------|------|

ตัวอย่างการใช้ bitwise OR ระหว่าง 16 และ 48 ซึ่งเป็นจำนวนเต็มขนาด 8 บิต

0 0 0 1 0 0 0 0  = 16
0 0 1 1 0 0 0 0  = 48
---------------	 OR
0 0 1 1 0 0 0 0  = 48
= = = = = = = = 

จากตัวอย่างพบว่ามีตำแหน่งที่เป็น 1 ทั้งหมด 2 ตำแหน่ง (มี 1 ตำแหน่งที่เป็น 1 ทั้งคู่ และอีก 1 ตำแหน่งที่มี 48 เป็น 1) ดังนั้นผลลัพธ์จึงเท่ากับ 48

bitwise XOR

bitwise XOR หรือ bitwise exclusive OR เป็นตัวดำเนินการทางตรรกศาสตร์แบบ OR อีกประเภทหนึ่ง ในทางโปรแกรมมิ่งมักแทนด้วยสัญลักษณ์ ^ การทำงานนั้นเหมือนกับ inclusive OR เลย เว้นแต่ถ้าตำแหน่งไหนเป็น 1 ทั้งคู่ จะคืนค่าตำแหน่งนั้นเป็น 0

|------|------|------|
|   A  |   B  | A ^ B|
|------|------|------|
|   1  |   1  |   0  |
|   1  |   0  |   1  |
|   0  |   1  |   1  |
|   0  |   0  |   0  |
|------|------|------|

ตัวอย่างการใช้ bitwise XOR ระหว่าง 16 และ 48 ซึ่งเป็นจำนวนเต็มขนาด 8 บิต

0 0 0 1 0 0 0 0  = 16
0 0 1 1 0 0 0 0  = 48
---------------  XOR
0 0 1 0 0 0 0 0  = 32
= = = = = = = = 

จากตัวอย่างจะเห็นว่ามีเพียงตำแหน่งเดียวที่เป็น 1 เหมือนกัน ดังนั้นที่ตำแหน่งนั้นจะได้ 0 นอกนั้นตำแหน่งไหนมี 1 ก็ดึงลงมาใส่ผลลัพธ์ ก็จะได้คำตอบเป็น 32

bitwise NOT

bitwise NOT เป็นตัวดำเนินการทางตรรกศาสตร์ตัวสุดท้าย แทนด้วยสัญลักษณ์ ~ bitwise ตัวนี้ต่างจากตัวอื่นที่กล่าวมาตรงที่มันต้องการ operand แค่ตัวเดียว และทำงานโดยการกลับบิต จาก 0 เป็น 1 จาก 1 เป็น 0 แค่นั้นเลย

|------|------|
|   A  |  ~A  |
|------|------|
|   1  |   0  |
|   0  |   1  |
|------|------|

ตัวอย่างการใช้ bitwise NOT กับเลข 16 ซึ่งเป็นจำนวนเต็มขนาด 8 บิต

0 0 0 1 0 0 0 0  = 16
---------------  NOT
1 1 1 0 1 1 1 1  = -17
= = = = = = = = 

เมื่อทำการกลับบิตของ 16 แล้วจะได้ 11101111 ซึ่งถ้าเราอ่านแบบปกติก็จะมีค่า 239 (255-16) แต่ถ้าเราพิจารณาว่ามันเป็น signed number นะ ก็จะได้เป็น -17 (เมื่อใช้วิธีเก็บแบบ Two's complement คือ เมื่อลบออก 1 แล้วกลับบิตด้วย NOT อีกครั้งจะพบว่าได้ 17)

left shift

left shift เป็นตัวดำเนินการพิเศษ เขียนแทนด้วยสัญลักษณ์ << รับ operand 2 ตัว คือค่าที่ต้องการ shif และทำนวนครั้งของการ shif การทำงานนั้นจะแปลกกว่าตัวอื่นที่กล่าวมาแล้ว คือ left shift จะเป็นการเลื่อนทุกบิตไปทางซ้าย n ครั้ง โดยตำแหน่งด้านขวาที่หายไปให้เติม 0 เข้ามาแทนที่

ตัวอย่างการทำ left shift 2 ตำแหน่ง กับเลข 16 ซึ่งเป็นจำนวนเต็มขนาด 8 บิต

    0 0 0 1 0 0 0 0  = 16
                0 0  = 2 shif
    ---------------  left shift
0 0 0 1 0 0 0 0 0 0  = 64
= = = = = = = = = =

จากตัวอย่างเมื่อเราทำการเลื่อนตำแหน่งครั้งแรก ค่าที่ได้คือ 32 และเมื่อเลื่อนอีกครั้งก็จะได้ผลลัพธ์เป็น 64 แล้วถ้าเราเลื่อนอีกครั้งล่ะ? ตามหลักของ Two's complement ก็จะได้ -128 ครับ แล้วถ้าเลื่อนอีก?

        0 0 0 1 0 0 0 0  = 16
                0 0 0 0  = 4 shif
        ---------------  left shift
0 0 0 1 0 0 0 0 0 0 0 0  = 0
= = = = = = = = = = = =

ครับ สรุปว่าเลื่อนแล้ว overflow ไปเลยครับ เหลือแต่ เลข 0 (บิตที่เกินออกไปทางด้านซ้ายจะหายไปหมด)

right shift

right shift เป็นตัวดำเนินการตัวสุดท้ายที่เราจะพูดถึงครับ ทำงานเหมือน left shift เป๊ะ แต่เลื่อนไปทางขวาแทน

ตัวอย่างการทำ right shift 2 ตำแหน่ง กับเลข 16 ซึ่งเป็นจำนวนเต็มขนาด 8 บิต

    0 0 0 1 0 0 0 0  = 16
                0 0  = 2 shif
    ---------------  right shift
0 0 0 0 0 0 0 1 0 0  = 4
= = = = = = = = = =

ก็น่าจะพอเดาออกกันครับว่าพอเราเลื่อนครั้งแรก ก็จะเหลือ 8 แล้วพอเลื่อนอีกครั้งนึงก็จะเหลือ 4 นั่นเอง

น่าจะพอเห็นภาพกันนะครับ ว่าการเทำ left shift ก็คือการคูณด้วย 2 และการทำ right shif ก็คือการหาร 2 นั่นเอง

รู้แล้วเอาไปทำอะไรได้?

ต้องบอกกอ่นว่าการทำ Bitwise operations หนึ่งครั้ง้นเกิดขึ้นเร็วมากเพราะเป็นแค่การเทียบค่า การกลับบิต หรือการเลื่อนๆ เฉยๆ และ operation เหล่านี้แหละครับที่อยู่เบื้องหลังการคำนวณทั้งหมดทั้งมวลของคอมพิวเตอร์เลย แต่ถ้าถามว่าในฐานะโปรแกรมเมอร์ธรรมดาๆ เอาไปทำอะไรดี ผมว่าก็น่าจะประมาณ

  • Bit fields (flags) หลายคนอาจจะเคยเห็นระบบ ACL ใน *NIX เช่นพวกเลข 777, 775 อะไรแบบนี้ ซึ่งมันอัศจรรย์มากที่ตัวเลข 3 ตัวนี้บอกได้เลยว่าใครสามารถอ่านเขียนหรือรันไฟล์ได้ จริงๆ แล้วตัวเลขแต่ละตัวเราเรียกว่า Bit fields ครับ ถ้าเป็น 7 หรือหมายถึง 1 1 1 ไงครับ ถ้าระบบจะถามหาสิทธ์ในการอ่านก็เช็คที่ตำแหน่งที่ 1 จากทางซ้าย ถ้าอากรู้ว่าเขียนได้ไหมก็เช็คที่ตำแหน่ง 2 ถ้าอยากรู้ว่า execute ได้ไหมก็เช็คที่ตำแหน่งขวาสุด เห็นมั้ยครับไม่ได้มีอะไรเป็น magic เลย

  • checksums, parity, stop bits พวกนี้ใช้สำหรับการตรวจสอบข้อมูลครับ มักใช้เมื่อมีการสื่อสารผ่าน protocol ต่างๆ วิธีการก็แค่ทำ bitwise operation บางอย่าง แล้วเอาผลที่ได้แปะไปกับข้อมูลเลย แล้วฝั่งผู้รับก็เอาข้อมูลทั้งสองส่วนมาตรวจสอบว่าถูกต้องไหม

  • Compression, Encryption การบีบอัดหรือเข้ารหัสก็ใช้ได้ครับเนื่องจาก Bitwise operations นั้นทำงานได้รวดเร็วจึงเหมาะที่จะนำไปใช้

  • State Machines ชิพหรือเครื่องจักรต่างๆ ที่มี state ทั้งหลาย ก็เป็นสิ่งที่มีการใช้ Bitwise operations เช่นกันครับ โดยเฉาะคอมพิวเตอร์ที่เราใช้ๆ กันอยู่ก็มีแผงวงจรที่ทำงานโดยใช้ Bitwise operations ทั้งสิ้น

  • Graphics อันนั้ชัวร์ครับ การทำ inverse การเพิ่มระดับสี ก็ล้วนใช้ Bitwise operations ทั้งนั้นครับ

References

‪#‎day35 #365วันแห่งโปรแกรม ‪#‎โครงการ365วันแห่ง‬...