เชี่ยวชาญ Bitwise Toolbox ของ Ruby: Operators, การประยุกต์ใช้ และ เทคนิคฉลาด

คุณอาจใช้ชีวิตสร้าง Rails apps ตลอดไปโดยไม่ต้องใช้ bitwise operators เลย หากคุณเพิ่งเริ่มเขียนโปรแกรม อาจไม่รู้ว่า "bitwise" หมายถึงอะไร

แต่เมื่อคุณเริ่มสนใจระบบที่ efficiency สำคัญและทรัพยากรจำกัด bitwise operations จะกลายเป็นสิ่งสำคัญ ใช้กันอย่างกว้างขวางกับ network protocols, cryptography, Unix file permissions และ embedded systems

นอกจากนี้ เพื่อเข้าใจจริงว่าคอมพิวเตอร์ทำอย่างไรเมื่อบวกเลขสองจำนวน คุณต้องเข้าใจ bitwise operations

เนื่องจาก Ruby และภาษาอื่นๆ รองรับแบบ native มันจึงเป็นเครื่องมือดีที่ควรเพิ่มใน toolbox แม้แค่เพื่อเข้าใจเมื่อพบในอนาคต

ในบทความนี้ เราจะครอบคลุม bitwise operations คืออะไร ตัวอย่างการประยุกต์ใช้ และวิธีใช้ใน Ruby มาเริ่มกัน

Bitwise operations คืออะไร?

ในระดับต่ำสุดของคอมพิวเตอร์ เรามีแค่ 1 และ 0 หรือที่เรียกว่า bits การดำเนินการอื่นๆ ใน Ruby หรือภาษาอื่นๆ สุดท้ายจะถูกเก็บเป็น 1 และ 0 แต่ซอฟต์แวร์ในคอมพิวเตอร์แปลงกลับมาอย่างมีประสิทธิภาพระหว่างสิ่งที่เราเห็นและสิ่งที่จัดเก็บจริง ตัวอย่าง เราเก็บ string "hello" เป็น chain ของ 1 และ 0

Bitwise operations ให้เราเข้าถึง bits เหล่านั้นโดยตรง (มักแทนตัวเลข) และทำ "บางอย่าง" กับพวกมัน บาง operations ช่วย implement features ในซอฟต์แวร์ได้อย่างขลังและมีประสิทธิภาพมากขึ้น

มี 2 ด้านสำคัญของ bitwise operations: มีประสิทธิภาพมากในการเก็บข้อมูล เนื่องจากใช้ bits โดยตรง และรันเร็วมาก

พฤติกรรมพื้นฐานคือมีชุด bits และนำ operator ไปใช้ ก็สามารถใช้ operators กับ 2 ชุด bits ได้ มาดู operations บางอย่าง:

NOT bitwise operation

นี่คือ unary operation หมายถึงใช้กับชุด bits เดียว และง่ายมากคือแทนที่ 1 ด้วย 0 และในทางกลับกัน แทนด้วยสัญลักษณ์: ~

~101000 = 010111

AND bitwise operation

AND เป็น operation ที่ใช้กับ 2 ชุด bits สัญลักษณ์คือ & และทำตามตรรกะนี้:

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

ดังนั้นเมื่อมี 2 ชุด bits ความยาวเท่ากัน ผลลัพธ์คือนำตรรกะนี้ไปใช้กับแต่ละคู่:

0110 AND 0111
-----
0110

ใน Ruby:

25.to_s(2) # 11001
30.to_s(2) # 11110
(25 & 30).to_s(2) # 11000

OR bitwise operation

คล้าย AND operation อีก operation ที่ใช้กับ 2 ชุด bits คือ bitwise OR สัญลักษณ์ | ตรรกะ:

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

ถ้ามี 1 ด้านไหนด้านหนึ่ง ผลลัพธ์คือ 1 ไม่เช่นนั้น 0 มาดู OR operation กับ bits มากขึ้น:

0110 OR 0111
-----
0111

ใน Ruby:

25.to_s(2) # 11001
30.to_s(2) # 11110
(25 | 30).to_s(2) # 11111

ตัวอย่างปฏิบัติ 1: Permissions (สิทธิ์)

ถึง đâyคุณอาจสงสัยว่าทำไม operations เหล่านี้ถึงมีประโยชน์ ดูเหมือน low-level มาก คุณอาจไม่มีแผนทำงานกับ network protocols, graphics หรือ cryptography โดยตรง

แต่คุณอาจเคยทำงานกับ permissions มาก่อน Permissions เป็นพื้นที่ที่ bitwise operations มีประโยชน์มาก จินตนาการระบบสิทธิ์ที่ผู้ใช้ทำ actions ต่างๆ ในเอกสารได้:

• View (ดู)
• Edit (แก้ไข)
• Delete (ลบ)
• Invite other users (เชิญผู้ใช้อื่น)

ตอนนี้เราต้องการ model actions เหล่านี้เป็น roles ต่างๆ:

• Assistant: ดูและแก้ไขเอกสารได้
• Observer: ดูเอกสารอย่างเดียว
• Author: ทำ actions ทั้งหมดได้

เราจะ model ยังไง? เรารู้ได้ยังไงว่าผู้ใช้มี role ใด? คำตอบหนึ่งคือใช้ bitwise operations

เราจะเก็บชุด bits เดียวสำหรับแต่ละ user แทน permissions ที่มี:

(เริ่มจากด้านขวา)
1st bit: View
2nd bit: Edit
3rd bit: Delete
4th bit: Invite other users

ตัวอย่าง:

0001 = ดูเอกสารอย่างเดียว
0011 = ดูและแก้ไขเอกสารได้
1001 = ดูได้ แก้ไขไม่ได้ ลบไม่ได้ แต่เชิญคนอื่นได้

เมื่อตั้งค่าเหล่านี้ให้ผู้ใช้บางคน เราสามารถเปรียบเทียบได้เร็วมากกับ permission ที่ต้องการ จินตนาการว่าเราตรวจสอบว่าผู้ใช้แก้ไขเอกสารได้หรือไม่ ใช้ bitwise AND operation:

# เรียกว่า bit mask มีแค่ค่าที่ต้องการตรวจสอบ ในกรณีนี้ bit ที่ 2 สำหรับ edit
EDIT_PERMISSION_MASK = 0b0010

# กำหนด method ตรวจสอบเร็ว:
def can_edit_document?(user_permissions)
  (EDIT_PERMISSION_MASK & user_permissions) != 0
end

หมายความว่าถ้า bitwise AND operation ให้ค่าอื่นนอกจาก 0 เราก็มี bit นั้นตั้งไว้:

0010 AND 1101
----
0000 == 0 ดังนั้นไม่มี permission

0010 AND 1110
----
0010 != 0 ดังนั้นมี permission

เราสามารถนำตรรกะเดียวกันไปใช้กับ permission อื่นๆ โดยเปลี่ยนตำแหน่ง bit ที่ต้องการตรวจสอบ จะได้ constants และ methods ตามนี้:

VIEW_PERMISSION_MASK = 0b0001
EDIT_PERMISSION_MASK = 0b0010
DELETE_PERMISSION_MASK = 0b0100
INVITE_PERMISSION_MASK = 0b1000

นอกจากนี้ เราสามารถกำหนด permissions แบบ dynamic และเก็บ permissions ใหม่ในอนาคตด้วย bit check เร็วๆ

เช่น เราบอกว่า assistant ดูและแก้ไขอย่างเดียว permissions คือ 0011 เก็บค่านี้ใน database แล้วตรวจสอบง่ายๆ ว่า assistant ทำ action ได้ไหมด้วย methods ที่กำหนด

ASSISTANT_MASK = VIEW_PERMISSION_MASK | EDIT_PERMISSION_MASK # จะเป็น: 0011

# อาจใช้ method นี้เช็คว่า user นี้เป็น assistant
def is_assistant?(user)
  (user.permissions == ASSISTANT_MASK)
end

ถ้าทั้งนี้ดูคุ้นเคย นั่นเพราะมันคือแนวทางเดียวกันที่ใช้กับ file permissions ใน Unix-based systems

ตัวอย่างปฏิบัติ 2: ตำแหน่งในทีม

มใช้ bitwise operations อีกนิด 😉

เราสามารถนำไปประยุกต์ในกรณีที่พบบ่อยอีก: ตำแหน่งต่างๆ ในทีมกีฬา หรือตำแหน่งงานในบริษัท มาใช้ทีมบาสเกตบอลเพื่อความเรียบง่าย

ในบาสเกตบอล มี 5 ตำแหน่งขณะเล่นเกม: - Point guard - Shooting guard - Small forward - Power forward - Center

กำหนดชุด bits ให้แต่ละตำแหน่ง: 00001 Point guard 00010 Shooting guard 00100 Small forward 01000 Power forward 10000 Center

ใน Ruby:

POINT_GUARD_POSITION = 0b00001
SHOOTING_GUARD_POSITION = 0b00010
SMALL_FORWARD_POSITION = 0b00100
POWER_FORWARD_POSITION = 0b01000
CENTER_POSITION = 0b10000

POINT_GUARD_POSITION | SHOOTING_GUARD_POSITION | SMALL_FORWARD_POSITION | POWER_FORWARD_POSITION | CENTER_POSITION
# = 31

ตอนนี้เราทำสิ่งน่าสนใจได้ เช่น เช็คว่าทีมครบหมดด้วย:

# p1...p5 คือตำแหน่งของแต่ละผู้เล่น
is_full_team_present = (p1 | p2 | p3 | p4 | p5 == 31)

ทำไม? ด้วย bitwise OR operation ถ้ามีตำแหน่งครบ เราจะได้: 11111

# OR bitwise operation
00001 | 00010 | 00100 | 01000 | 10000
-----
11111

และ 11111 คือ 31 เพราะ 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31

ไม่เกี่ยวกับ bitwise operations โดยตรง แต่ด้วย data modeling นี้ เรายังเช็คได้ว่าผู้เล่น 2 คนสลับกันได้หรือไม่ ซึ่งง่ายมาก:

def can_be_exchanged?(player1, player2)
  player1.position == player2.position
end

XOR

Operation อีกอย่างกับ 2 ชุด bits คือ XOR สัญลักษณ์ ^

XOR ย่อมาจาก exclusive OR ตรรกะ:

1 | 1 = 0
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

ผลลัพธ์จะเป็น 1 ก็ต่อเมื่อ bit หนึ่งในสองเป็น 1 ถ้าทั้งคู่เท่ากันจะเป็น 0

Operation นี้ใช้ในบางอัลกอริทึมเปรียบเทียบตัวเลขกับตัวมันเอง เนื่องจาก x ^ x = 0

Shifts (การเลื่อน)

กลุ่ม operations น่าสนใจที่เรา "เลื่อน" bits ไปด้านหนึ่งหรืออีกด้านในชุดหนึ่ง มาอธิบาย

กับ bit shift เราเลื่อน bits ไปทิศทางหนึ่ง ซ้ายหรือขวา:

00010111 left-shift <------- 00101110

10010111 right-shift -------> 11001011

เราเลื่อน bits n ครั้ง นี่คือ left shift ใช้กับเลข 5 สองครั้งใน Ruby:

5.to_s(2) # 101
(5 << 2).to_s(2) # 10100

เห็นได้ว่า left shift แทนด้วย << right shift ใช้ >>:

5.to_s(2) # 101
(5 >> 2).to_s(2) # 1

ในกรณีนี้ได้แค่ 1 เพราะ bits "0" และ "1" จาก 1*01* ถูกทิ้ง

หาร 2 ด้วย right shift

ข้อเท็จจริงน่าสนใจของ bit shifts คือคุณคำนวณ operations คณิตศาสตร์บางอย่างได้ด้วยในอดีตเร็วกว่า แต่ตอนนี้ใช้เกือบเฉพาะโปรแกรมเมอร์ที่ทำงานภายใต้ข้อจำกัดทรัพยากร เช่น game development

ถ้า right shift ตัวเลข จะได้ผลหาร 2:

10.to_s(2) # 1010
(10 >> 1).to_s(2) # 101
10 >> 1 # 5

คูณ 2 ด้วย left shift

เช่นเดียวกัน คูณ 2 ด้วย left shift:

10.to_s(2) # 1010
(10 << 1).to_s(2) # 10100
10 << 1 # 20

ตรวจสอบเร็วว่าเลขคู่หรือคี่

มีตัวอย่าง bitwise operation เรียบง่ายที่เร็วมากและเข้าใจง่าย

จินตนาการเราทำ AND operation กับ 1 แค่ 1 นั่นคือ 0s จำนวนมาก (ขึ้นกับคอมพิวเตอร์) และ 1 มาลองกับ 2:

2 = 00000010
& 00000001
-------------
00000000

ลองกับ 4:

4 = 00000100
& 00000001
-------------
00000000

5 นะ?

5 = 00000101
& 00000001
-------------
00000001

ตอนนี้ได้ 1 ทายได้ไหมว่าหมายถึงอะไร?

ทำ AND กับ 1 ถ้าเลขคู่ จะได้ 0 ถ้าคี่ จะได้ 1 เราสร้าง methods ใน Ruby ได้ง่าย:

def is_odd?(number)
  number & 1
end

def is_even?(number)
  is_odd?(number) == 0
end
# หรือ:
def is_even?(number)
  (number & 1) == 0
end

อยากลึกขึ้น หรือประสบการณ์ mind-blowing กับ bits ดู bitwise hacks collection สำหรับเทคนิคเพิ่มเติม

สรุป

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