เรื่องที่อยากเขียน ... เรื่องที่พยายามเขียน ...
Group Blog
 
All blogs
 
เรื่องของ XOR


วันนี้มาย้อนอดีตสมัยเรียน math เรื่องของ Exclusive Or หรือ XOR กันหน่อยนะครับ
XOR เป็น logical operation ที่มี truth table เป็น

 A  B XOR
000
011
101
110

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.

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


โดย: AIam วันที่: 29 กันยายน 2551 เวลา:21:08:03 น.  

 
เจ๋งอะ ขอบคุณมากครับ


โดย: ไอซ์ IP: 58.137.97.178 วันที่: 6 ตุลาคม 2551 เวลา:11:41:08 น.  

 
อยาก xor byte อะแต่มันเออเร่อ
คืออยากจะรู้ว่า 112 หรือ 70ในไบท์ xor อะไรจะได้ 15
เลยเขียนโปรแกรมดูแต่ไม่ค่อยเข้าใจ

Private Sub Button3_Click() Handles Button3.Click
Dim b As Byte = CByte(112) '##70 Xor อะไรได้ 15
Dim a(255) As Byte
Dim m As String = ""
For i As Short = 0 To 255
a(i) = CByte(i)
a(i) = b ^ i
m &= a(i).ToString & " = " & i.ToString _
& ControlChars.CrLf
Next
TextBox2.Text = m
End Sub

เขียนเป็น c ก็ได้ เราอ่านออก


โดย: ช่วยเหลือหน่อยแน IP: 124.120.233.7 วันที่: 1 พฤศจิกายน 2551 เวลา:18:18:08 น.  

 
จากสามเหลี่ยมของ XOR ครับ
ูa^b = c
a^c = b
ถ้า a=112, c=15 หา b ได้จาก
b = a^c = 112^15 = 127



โดย: zkaru วันที่: 4 พฤศจิกายน 2551 เวลา:7:53:51 น.  

 
แล้วถ้ามันไม่ได้ตามสูตรหละ
คือ เรารู้ว่า เลขฐาน16แต่ละตัว
ที่เข้ารหัสไว้ มีค่าเท่าไหร่ แต่ เราหาสูตรแก้กลับไม่ได้ อะจิ
เลขพวกนี้เรียงกันตั้งแต่ 0-256 ค่ามันเริ่มเพี้ยนๆตั้งแต่ 04
ไม่รู้ว่ามันเข้ารหัสแบบไหนไว้ กว่าเราจะได้ค่ามาเรียงกันได้แบบนี้ค่อนข้างนาน ใช้ความอดทนสุดๆ อิอิ อ่านแล้วแอดมินช่วยลบออกให้สั้นด้วยเน้อ

00
01
02
03
0c
0d
0e
0f
08
09
0a
0b
74
75
76
77
70
71
72
73
7c
7d
7e
7f
78
79
7a
7b
64
65
66
67
60
61
62
63
6c
6d
6e
6f
68
69
6a
6b
54
55
56
57
50
51
52
53
5c
5d
5e
5f
58
59
5a
5b
44
45
46
47
40
41
42
43
4c
4d
4e
4f
48
48
4a
4b
b4
b5
b6
b7
b0
b1
b2
b3
bc
bd
be
bf
b8
b8
b9
ba
bb
a4
a5
a6
a7
a0
a1
a2
a3
ac
ad
ae
af
a8
a9
aa
ab
94
95
96
97
90
91
92
93
9c
9d
9e
9f
98
99
9a
9b
84
85
86
87
80
81
82
83
8c
8d
8e
8f
88
89
8a
8b
f4
f5
f6
f7
f0
f1
f2
f3
fc
fd
fe
ff
f8
f9
fa
fb
e4
e5
e6
e7
e0
e1
e2
e3
ec
ed
ee
ef
e8
e9
ea
eb
d4
d5
d6
d7
d0
d1
d2
d3
dc
dd
de
df
d8
d9
da
db
c4
c5
c6
c7
c0
c1
c2
c3
cc
cd
ce
cf
c8
c9
ca
cb
34
35
36
37
30
31
32
33
3c
3d
3e
3f
38
39
3a
3b
24
25
26
27
20
21
22
23
2c
2d
2e
2f
28
29
2a
2b
14
15
16
17
10
11
12
13
1c
1d
1e
1f
18
19
1a
1b
04
05
06
07


โดย: ช่วยเหลือหน่อยแน IP: 124.120.243.122 วันที่: 6 พฤศจิกายน 2551 เวลา:2:01:00 น.  

 
ได้คำตอบแล้ว
อิอิ 55+
Xor ซ้อน Or


โดย: ช่วยเหลือหน่อยแน IP: 124.120.236.164 วันที่: 7 พฤศจิกายน 2551 เวลา:16:48:09 น.  

 
My coder is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he's tryiong none the less. I've been using WordPress on numerous websites for about a year and am worried about switching
to another platform. I have heard very good things about blogengine.net.
Is there a way I can transfer all my wordpress posts into it?
Any help would be really appreciated!
ข้อดีของคาสิโนออนไลน์ 2022 คืออะไร?


โดย: Felipa IP: 49.228.178.114 วันที่: 23 พฤษภาคม 2565 เวลา:14:55:34 น.  

 
ในปี 2565 ทุกท่านที่ประสบเขอกับปัญหาในเรื่องที่เกี่ยวข้องกับการเงินจะหมดไปเมื่อได้ลงทุนกับ playslot888.com ผู้ให้บริการเว็บสล็อตแตกง่าย 2022 ไม่ผ่านเอเย่นต์ ที่จะสร้างรายได้ออนไลน์ ผ่านเกมสล็อตออนไลน์ซึ่งสามารถหารายได้ได้จริง
มีเกมแตกง่ายให้เลือกเล่นล้นหลามหลายค่าย จากเว็บตรงpg,เว็บตรงสล็อตxo,
slot live22,สล็อตค่ายโจ๊กเกอร์,ซุปเปอร์สล็อต,
slot jili,pragmatic play ซึ่งมีให้เลือกเล่นมากยิ่งกว่า 300 เกมส์ เลยทีเดียว ซึ่งการเล่นของทุกท่านจะไม่ผ่านตัวกลางใดๆ เล่นได้โดยตรง ไได้รับการรับรองจากหน่วยงานต่างแดนมากมาย ไม่ว่าจะเป็น GAMBLING COMMISSION ซึ่งเป็นหน่วยงานที่ควบคุมเกี่ยวกับเว็บพนันออนไลน์โดยตรง
เพื่อไม่ให้ผู้ใช้บริการนั้นโดยการเอาเปรียบ เว็บตรงไม่ผ่านเอเย่นต์แตกง่ายของเรานั้น
ไม่มีการดัดแปลงปรับปรุงแก้ไขตัวเกมแต่อย่างใด เล่นง่าย แตกง่ายแตกบ่อยมาก ไม่เหมือนเว็บไซต์อื่นๆที่ท่านเคยเล่นมาอย่างไม่ต้องสงสัย มีระบบที่จะเพิ่มความสะดวกให้กับสมาชิกอย่าง สล็อตฝากถอนออโต้
ที่เร็วไว ใช้เวลาไม่นานไม่เกิน 15 นาที
อีกทั้งยังรองรับslot บัญชี wallet โดยไม่จำเป็นต้องใช้บัญชีธนาคาร อีกทั้งยังจัดเต็มไปด้วยโปรสล็อตสมาชิกใหม่
และยังเอาอกเอาใจผู้ที่มีทุนน้อย ที่จะฝากเงินรับโบนัสฟรีๆ อย่างโปร ฝากครั้งแรก 100,
slot โปรฝาก20รับ100 สำหรับท่านที่พึงพอใจอยากมีรายได้พิเศษผ่านหนทางออนไลน์ วันนี้ playslot888.com เปิดให้บริการสมัครเว็บสล็อต เข้ามาเปิดประสบการณ์ รวมบันเทิงใจได้ตลอด 24 ชั่วโมง ไม่มีวันหยุด และสำหรับใครที่ยังเป็นมือใหม่ เรามีบทความ รีวิวเกมสล็อตได้เงินจริง
ซึ่งมีเกมดังมากมายอย่างเช่น วัวทอง,สล็อตบ้านขนมหวาน,สล็อตกัวกระโหลก สามารถอ่านได้ฟรี เพิ่มโอกาสให้ เล่นเว็บสล็อตไม่ผานเอเย่นต์
แตกง่าย แตกบ่อย ได้มากยิ่งขึ้น
ฝากผ่านวอเลท


โดย: Tristan IP: 206.232.52.74 วันที่: 18 กรกฎาคม 2565 เวลา:2:55:51 น.  

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 

zkaru
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 2 คน [?]




เรื่องที่อยากเขียน ... เรื่องที่พยายามเขียน ...
Friends' blogs
[Add zkaru's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.