เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ

โอกาสที่ต้องทำ bitwise math ในงานประจำวันน้อยมาก Ruby bitwise AND/OR operators (& และ |) ใช้โดยบังเอิญมากกว่าใช้จริง ใครไม่เคยพิมพ์ & ตอนที่อยากพิมพ์ &&?

แต่ถ้าโตมากับ lower-level languages เช่น C, Assembler หรือในกรณีผมคือ Turbo Pascal น่าจะเคย bit twiddling บ้าง

Bitwise solutions สวยงาม ถ้าแก้ปัญหาด้วย basic operations ที่คอมพิวเตอร์ทำได้ (binary math) ไม่ได้ elegant กว่านี้แล้ว

จัดการ Binary ใน Ruby

คุณรู้ว่าในคอมพิวเตอร์ทุกอย่างแทนด้วยตัวเลข และตัวเลขอยู่ใน binary format แต่มันดูยังไงใน Ruby? ตัวอย่างผม lookup ASCII char code ของ "a" แล้ว print เป็น "binary"

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ ใช้ ord method ได้ ASCII code แล้ว printf print binary representation

แม้ต้องใช้ printf แสดง binary แต่มันเป็น binary มาตลอด เขียน binary literals ใน Ruby code ได้ด้วย syntax 0b11111111

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ เพิ่ม binary literals: prefix string ของ 0 และ 1 ด้วย 0b เช่น 0b11111111

จัดการ Binary Values

ตอนนี้รู้ binary literals แล้ว เริ่มเล่นกับ bitwise operators ได้

คุณคุ้นเคย boolean operators เช่น && expression a && b return true ก็ต่อเมื่อ a และ b true ทั้งคู่ Bitwise operators คล้ายกันมาก

Bitwise AND รับ 2 values เปรียบเทียบ bit โดย bit ถ้าทั้งคู่เป็น 1 output bit = 1 ไม่งั้น 0 ถ้ามี 8 bits จะมี 8 ANDs แยกกัน ถ้า 1 bit มี 1 AND ตัวอย่าง illustrate ด้วย single bit

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ ตัวอย่าง bitwise AND operations กับ single bit

2 bits ก็เหมือนกัน

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ แต่ละคู่ bits ถูก and แยกกัน

Bitwise Operators ของ Ruby

เกือบทุก language มีชุดนี้ ถ้ายังไม่คุ้น ลองเล่นใน IRB นิดหน่อย จะใช้ได้ตลอดชีวิต

&	Bitwise AND Operator ตั้ง result bit = 1 ถ้าเป็น 1 ในทั้ง 2 input values	`0b1010 & 0b0111 == 0b0010`
\|	Bitwise OR Operator ตั้ง result bit = 1 ถ้าเป็น 1 ใน input ใด input หนึ่ง	`0b1010 \| 0b0111 == 0b1111`
^	Bitwise XOR Operator ตั้ง result bit = 1 ถ้าเป็น 1 ใน input ใด input หนึ่ง แต่ไม่ใช่ทั้งคู่	`0b1010 \| 0b0111== 0b1101`
~	Bitwise Inverse operator ตั้ง result bit = 0 ถ้า input เป็น 1 และ vice versa	`~0b1010 == 0b0101`
<<	Bitwise Left Shift Operator เลื่อน input bits ซ้าย จำนวน places ที่ระบุ	`0b1010 << 4== 0b10100000`
>>	Bitwise Right Shift Operator เลื่อน input bits ขวา จำนวน places ที่ระบุ	`0b1010 >> 4 == 0b0000`

Practical Use: Configuration Flags

Ok นี่เป็นการใช้ bitwise math ที่ boring ที่สุด แต่มัน common มาก ถ้า interface กับ Java, C, C++ จะเจอ bitwise configuration flags

สมมติปี 1996 คุณสร้าง database system เอง ดูหนัง Hackers คิดว่าควรมี access control

มี 8 actions ที่ user ทำได้: read, write, delete และอีก 5 ตัว อยากตั้งแต่ละอันแยกได้ User อ่านได้แต่มีเขียน/ลบไม่ได้ User เขียนได้แต่ drop tables ไม่ได้

เก็บ configuration flags อย่างมีประสิทธิภาพที่สุดคือเป็น bits ใน single byte User OR มารวมกันเพื่อสร้าง combination permissions ที่ต้องการ

MYDB_READ = 0b00000001 # ตัวเลขนี้เรียกว่า bitmasks MYDB_WRITE = 0b00000010 MYDB_DELETE = 0b00000100 MYDB_INDEX = 0b00001000 user.permissions = MYDB_READ | MYDB_WRITE

คล้ายกับ unix file permissions ถามว่าไมทำไมต้อง magic number เพื่อ read-only ตอนนี้รู้แล้ว

เก็บ config ใน bits ไม่ประโยชน์ถ้า detect ไม่ได้ว่า bit ไหน set ใช้ bitwise AND

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ ใช้ AND กับ bitmask ตรวจสอบว่า bit set หรือไม่

Less Practical Uses (เว้นแต่คุณเป็น C programmer)

มาทำ mathe-magical stuff บ้าง

Historically bit manipulation ใช้เวลาพยายาม擠 last fraction of millisecond จาก computation ใช้เยอะกับ graphics programmers และคนที่ต้องการ performance มากที่สุด

เทคนิคแบบนี้ไม่ practical สำหรับ Ruby development ทุกวัน แต่ยังเป็น fun learning exercise และอาจ useful ถ้าเข้า embedded systems programming รายละเอียดเพิ่มเติมดู bit twiddling hacks list

คูณ/หาร ด้วย Powers of Two

ดู binary representations ของ 1, 2, 4, 8 การ double = shift bits ซ้าย 1 place การ half = shift ขวา

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ Binary representations ของ 1, 2, 4, 8

เรามี shift-left/right operators คูณ/หาร powers of two ได้โดยแค่ shift bits

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ ใช้ bitwise shift operators คูณ/หาร powers of two

Average ของ Positive Integers 2 ตัว

Addition 基本: (x+y) == (x&y)+(x|y) == (x^y)+2*(x&y) หา average ต้องการแค่หาร 2 ได้จาก right shift operator

เชี่ยวชาญ Bitwise Operations ใน Ruby: เทคนิคและทริคต่างๆ Average 2 positive integers: (x&y)+((x^y)>>1)

Fast Inverse Square Root

ไม่สามารถข้าม legendary example นี้ได้ John Carmack fast inverse square root approximation จาก Quake 3 arena source code 1999 Algorithm ไม่ใช่ของเขา แต่ implementation ที่ famous ที่สุดคือของเขา

ไม่พยายาม port ตรงๆ มา Ruby เพราะมัน construct binary representation ของ floating point ใช้วิธีที่ไม่ translatable จาก C มา Ruby โดยตรง

float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, can be removed return y; }