|
เรื่องของ XOR
วันนี้มาย้อนอดีตสมัยเรียน math เรื่องของ Exclusive Or หรือ XOR กันหน่อยนะครับ XOR เป็น logical operation ที่มี truth table เป็น
XOR ที่ใช้ในโปรแกรมจะเป็นแบบ binary หรือ bitwise operation ไม่ใช่แบบ logical operation เราจะใช้สัญลักษณ์ ^ แทน XOR เหมือนที่ใช้ในภาษา C/C++, JAVA, C#
จาก truth table ด้านบน มีเรื่องน่าสนใจหลายเรื่องครับ
XOR จะเหมือนการบวกเลขฐานสองโดยที่ไม่นับทด ลองบวกเลขฐานสองดู 0+0 = 0 0+1 = 1 1+0 = 1 1+1 = 10 พอไม่นับทด 1+1 ก็จะเหลือแค่หลักเดียวคือ 0 1+1 = 0 จะเห็นได้ว่าผลลัพธ์เหมือนใน truth table ด้านบนเลย
XOR สามารถสลับตำแหน่งได้ พอ XOR เหมือนการบวก มันเลยมีลักษณะแบบเดียวกับการบวก คือ สามารถสลับตำแหน่ง หรือ ทำอะไรก่อนหลังได้ เช่น a^b^c a^c^b (a^b)^c a^(b^c) (a^c)^b จะได้ค่าเท่ากันหมด ภาษา math เรียกว่า commutativity กับ associativity (จำเค้ามาครับ)
XOR กับ 0 จะได้ค่าเท่าเดิม a^0 = a ไม่ว่า a จะเป็น 0 หรือ 1
XOR กับ 1 จะเป็นการกลับค่า a^1 = ~a เดิม a เป็น 0 ก็จะได้ค่าเป็น 1 เดิม a เป็น 1 ก็จะได้ค่าเป็น 0
XOR เอาไว้หาความต่าง ค่าที่เหมือนกัน XOR กันจะได้ 0 0^0 = 0 1^1 = 0 ค่าที่ต่างกัน XOR กันจะได้ 1 0^1 = 1 1^0 = 1
ค่าเหมือนกันนำมา XOR กัน ค่านั้นจะหายไป เช่น a^b^a สลับตำแหน่ง จะได้ a^a^b a^a (ค่าเหมือนกัน) จะได้ 0 0^b = b ดังนั้น a^b^a = b เหมือนเอา a มาฆ่า a
สามเหลี่ยมของ XOR ถ้า a^b แล้วได้ c เอา b^c จะได้ a และ c^a จะได้ b เป็นเหมือนรูปสามเหลี่ยม
แล้วเราใช้ XOR ทำอะไรกันบ้าง
นอกจากโปรแกรมคำนวนทาง math แบบลึกๆ หรือโปรแกรมที่ต้องเลียนแบบการทำงานของ hardware แล้ว เราแทบไม่ค่อยได้ใช้ XOR กันเลย ที่พอนึกออกคือ
ใช้เคลียร์ค่าให้เป็น 0 เช่น การเคลียร์ค่าของ register ax ในภาษา assembly xor ax, ax ถึงแม้ว่ามันจะทำให้ code อ่านยากสักหน่อย แต่นัยว่ามันเร็วกว่าการทำ mov ax, 0 ก็มันเป็นภาษา assembly ต้องการความเร็วครับ
ใช้กลับค่า (toggle) ให้ 0 เป็น 1 และให้ 1 เป็น 0 เช่น การกลับค่าของ bit 0 (ค่า 1) ถ้าไม่ใช้ XOR ก็ต้องเขียนประมาณนี้ if (f&1) f &= ~1; else f |= 1; ถ้าใช้ XOR ก็ statement เดียว f ^= 1;
ใช้สลับค่า (swap) เช่น function swap void swap(int *v1, int *v2) { *v1^=*v2; *v2^=*v1; *v1^=*v2; } หรือเขียนใหม่เป็น macro แบบนี้ #define SWAP(v1,v2) { (v1)^=(v2); (v2)^=(v1); (v1)^=(v2); }
ใช้หาความต่าง เช่นในการบีบอัดภาพเคลื่อนไหว เรามีภาพเป็น frame F1, F2, F3, ... ปรกติภาพในแต่ละ frame จะมีความแตกต่างกับ frame ที่อยู่ถัดไป ไม่มาก ถ้านำภาพ frame แรกมา XOR กับ frame ถัดไป pixel ที่เหมือนกันจะได้ค่าเป็น 0 pixel ที่ต่างกันจะได้ค่าเป็น 1 (หรือค่าอื่นที่ไม่เป็น 0) ผลคือ จะได้ 0 เป็นจำนวนมาก และที่ไม่เป็น 0 ในบริเวณที่มีการเคลื่อนไหว พอมี 0 ซะส่วนใหญ่ การบีบอัดก็จะทำได้ง่าย และมีขนาดเล็ก D1=F1^F2 D2=F2^F3 D3=F3^F4 ... ผลที่ได้ F1,D1,D2,D3.... ได้ frame แรก (F1) กับ D1,D2,D3.... ซึ่งแต่ละ Dn จะมีขนาดเล็ก เวลาขยายภาพกลับก็ทำโดยใช้ สามเหลี่ยมของ XOR คือ ในเมื่อ D1=F1^F2 ดังนั้น F2=F1^D1 และต่อๆไป F3=F2^D2 F4=F3^D3
ใช้ในการเข้ารหัสและถอดรหัส encrypt/decrypt สมมุติว่า P คือข้อความที่จะเข้ารหัส K คือ password หรือ key C คือข้อความที่เข้ารหัสแล้ว โดยที่ C=P^K จากสามเหลี่ยมของ XOR P=C^K พูดง่ายๆคือ เอาข้อความ XOR กับ key แล้วส่งไป ที่ปลายทางรับข้อความมาแล้ว XOR กับ key เดียวกัน จะได้ข้อความเดิมกลับมา
ถ้า key ที่ใช้เป็น true random number และใช้ (XOR) ครั้งเดียวแล้วทิ้ง วิธีการนี้จะเรียกว่า one-time pads ซึ่งเป็น algorithm ที่แข็งแรงที่สุด สมบูรณ์ที่สุด เลยครับ เล่ากันว่าโทรศัพท์ hotline ที่ใช้ระหว่างอเมริกากับอดีตสหภาพโซเวียตใช้ algorithm นี้
one-time pads ไม่ใช่ algorithm ที่ดีที่สุด เพราะการหา true random number ทำได้ยากมาก และยังต้องหาช่องทางที่ปลอดภัย (secure channel) ในการส่ง true random number ไปที่ปลายทาง รวมถึงการเก็บรักษาให้เป็นความลับที่สุด ตอนที่นำไปใช้แล้วก็ต้องทำลายทิ้ง มันเลยยุ่งยากและเสียค่าใช้จ่ายมาก
ถ้าปรับเปลี่ยน algorithm นิดหน่อย คือแทนที่จะใช้ true random number ก็ใช้ pseudo-random number แทน แล้วใช้ seed เป็น key ก็จะได้ stream cipher ที่แข็งแรงพอสมควร และเขียนโปรแกรมได้ง่าย code ไม่ซับซ้อน เอาไว้มีเวลาจะเอาตัวอย่างมาให้ดู
พวก cryptography นี่แหละ ไม่ว่าจะเป็น encrypt/decrypt, message digest, secure random generator, etc. จะใช้ XOR กันมากหน่อย
ใครมีเรื่องการใช้ XOR แบบอื่น มาเล่าสู่กันฟังบ้างนะครับ
Create Date : 26 กันยายน 2551 |
Last Update : 26 กันยายน 2551 22:01:42 น. |
|
8 comments
|
Counter : 11595 Pageviews. |
|
|
|
โดย: AIam วันที่: 29 กันยายน 2551 เวลา:21:08:03 น. |
|
|
|
โดย: ไอซ์ IP: 58.137.97.178 วันที่: 6 ตุลาคม 2551 เวลา:11:41:08 น. |
|
|
|
โดย: ช่วยเหลือหน่อยแน IP: 124.120.233.7 วันที่: 1 พฤศจิกายน 2551 เวลา:18:18:08 น. |
|
|
|
โดย: zkaru วันที่: 4 พฤศจิกายน 2551 เวลา:7:53:51 น. |
|
|
|
โดย: ช่วยเหลือหน่อยแน IP: 124.120.243.122 วันที่: 6 พฤศจิกายน 2551 เวลา:2:01:00 น. |
|
|
|
โดย: ช่วยเหลือหน่อยแน IP: 124.120.236.164 วันที่: 7 พฤศจิกายน 2551 เวลา:16:48:09 น. |
|
|
|
โดย: Felipa IP: 49.228.178.114 วันที่: 23 พฤษภาคม 2565 เวลา:14:55:34 น. |
|
|
|
โดย: Tristan IP: 206.232.52.74 วันที่: 18 กรกฎาคม 2565 เวลา:2:55:51 น. |
|
|
|
| |
|
|
แล้วก็ขออนุญาติ copy ไปให้เพื่อน ๆ อ่านด้วยนะครับ