แฮ็ก Bitwise ใน Ruby

โอกาสที่คุณไม่จำเป็นต้องทำการคำนวณระดับบิตในงานประจำวันของคุณ ตัวดำเนินการ AND และ OR ระดับบิตของ Ruby ( &และ | ) อาจถูกใช้โดยไม่ได้ตั้งใจมากกว่าที่ตั้งใจไว้ ใครไม่ได้พิมพ์โดยไม่ได้ตั้งใจ &เมื่อพวกเขาหมายถึง &&?

แต่ถ้าคุณโตมาโดยการเขียนโปรแกรมภาษาระดับล่าง เช่น C หรือ Assembler หรือในกรณีของฉัน Turbo Pascal อย่างน้อยคุณก็น่าจะทำให้งงบ้างเล็กน้อย

การแก้ปัญหาแบบ Bitwise นั้นยอดเยี่ยมมาก หากคุณสามารถแก้ปัญหาของคุณได้โดยใช้การดำเนินการพื้นฐานที่สุดที่คอมพิวเตอร์สามารถ (คณิตศาสตร์ไบนารี) ได้ มันก็จะไม่ได้สวยงามไปกว่านั้น

การทำงานกับไบนารีใน Ruby

คุณอาจรู้ว่าทุกอย่างในคอมพิวเตอร์ของคุณแสดงเป็นตัวเลข และตัวเลขเหล่านั้นอยู่ในรูปแบบไบนารี แต่สิ่งที่ดูเหมือนในทับทิม? ในตัวอย่างนี้ ฉันใช้ Ruby เพื่อค้นหารหัสถ่าน ASCII สำหรับตัวอักษร "a" แล้วพิมพ์เป็น "ไบนารี"

แฮ็ก Bitwise ใน Ruby คุณสามารถใช้ ord วิธีใน Ruby เพื่อรับรหัส ASCII ของตัวละคร จากนั้นใช้ printf เพื่อพิมพ์แทน "ไบนารี" ของมัน

แม้ว่าเราจะต้องใช้วิธีการเช่น printf เพื่อแสดงตัวเลขเป็นเลขฐานสอง แต่ก็เป็นเลขฐานสองเสมอ คุณเขียนเลขฐานสองในรหัส Ruby ได้โดยใช้ไวยากรณ์ เช่น 0b11111111 .

แฮ็ก Bitwise ใน Ruby หากต้องการเพิ่มตัวอักษรไบนารีลงในโค้ดของคุณ ให้เติม 0b นำหน้าสตริงของหนึ่งและศูนย์ ดังนั้น 0b11111111

การจัดการค่าไบนารี

ตอนนี้เรารู้วิธีใช้เลขฐานสองในทับทิมแล้ว เรามาเริ่มเล่นกันเลย ในการทำเช่นนั้น เราจะใช้ตัวดำเนินการระดับบิต

คุณอาจพอใจกับตัวดำเนินการบูลีนเช่น &&นิพจน์ a &&b คืนค่า จริง ต่อเมื่อ a และ b ทั้งคู่เป็นจริง ตัวดำเนินการระดับบิตนั้นคล้ายกันมาก

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

แฮ็ก Bitwise ใน Ruby ตัวอย่างการดำเนินการระดับบิต AND ด้วยบิตเดียว

มันทำงานเหมือนกันสำหรับสองบิต

แฮ็ก Bitwise ใน Ruby บิตแต่ละคู่แยกจากกัน

ตัวดำเนินการ Bitwise ของ Ruby

แทบทุกภาษาโปรแกรมจะมาพร้อมกับชุดตัวดำเนินการระดับบิตนี้ ถ้าคุณไม่คุ้นเคยกับพวกเขา ใช้เวลาสักเล็กน้อยใน IRB ทดลองพวกเขา เมื่อคุณเรียนรู้แล้ว คุณจะสามารถใช้งานได้ตลอดชีวิต

OperatorDescriptionExample

&	ระดับบิต และตัวดำเนินการ ตั้งค่าบิตของผลลัพธ์เป็น 1ถ้าเป็น 1 ในค่าอินพุตทั้งสองค่า	`0b1010 & 0b0111 == 0b0010`
\|	ตัวดำเนินการระดับบิตหรือตัวดำเนินการ กำหนดบิตของผลลัพธ์เป็น 1ถ้าเป็น 1 ในค่าอินพุตทั้งสองค่า	`0b1010 \| 0b0111 == 0b1111`
^	ตัวดำเนินการ XOR ระดับบิต ตั้งค่าบิตผลลัพธ์เป็น 1ถ้าเป็น 1 ในค่าอินพุตใดค่าหนึ่ง แต่ไม่ใช่ทั้งคู่	`0b1010 \| 0b0111== 0b1101`
~	ตัวดำเนินการผกผันระดับบิต ตั้งค่าบิตผลลัพธ์เป็น 0 หากอินพุตเป็น 1 และในทางกลับกัน	`~0b1010 == 0b0101`
<<	ตัวดำเนินการ Shift ซ้ายระดับบิต . ย้ายอินพุตบิตไปทางซ้ายตามจำนวนตำแหน่งที่กำหนด	`0b1010 << 4== 0b10100000`
>>	ตัวดำเนินการ Shift ขวาระดับบิต . ย้ายอินพุตบิตไปทางขวาตามจำนวนตำแหน่งที่กำหนด	`0b1010 >> 4 == 0b0000`

การใช้งานจริง:การตั้งค่าสถานะการกำหนดค่า

โอเค โอเค นี่จะต้องเป็นการใช้คณิตศาสตร์ระดับบิตที่น่าเบื่อที่สุด แต่ก็เป็นหนึ่งในสิ่งที่พบได้บ่อยที่สุด หากคุณต้องติดต่อกับโค้ดที่เขียนด้วยภาษา Java หรือ C หรือ C++ คุณจะพบกับการตั้งค่าสถานะระดับบิตในที่สุด

ลองนึกภาพว่านี่คือปี 1996 และคุณเพิ่งสร้างระบบฐานข้อมูลตั้งแต่เริ่มต้น เนื่องจากคุณเพิ่งดูหนังเรื่อง Hackers คุณจึงคิดว่าควรสร้างการควบคุมการเข้าถึงบางประเภท

มีการดำเนินการ 8 อย่างที่ผู้ใช้สามารถดำเนินการในฐานข้อมูลของคุณ:อ่าน เขียน ลบ และอีกห้ารายการ คุณต้องการตั้งค่าแต่ละรายการแยกจากกัน คุณอาจมีผู้ใช้ที่สามารถอ่านแต่เขียนหรือลบไม่ได้ คุณอาจมีโต๊ะที่เขียนได้แต่วางตารางไม่ได้

วิธีที่มีประสิทธิภาพที่สุดในการจัดเก็บแฟล็กการกำหนดค่าเหล่านี้จะเป็นแบบบิตในไบต์เดียว จากนั้นผู้ใช้จะ OR ร่วมกันเพื่อสร้างการอนุญาตที่พวกเขาต้องการ

MYDB_READ   = 0b00000001 # These numbers are called bitmasks
MYDB_WRITE  = 0b00000010
MYDB_DELETE = 0b00000100
MYDB_INDEX  = 0b00001000

user.permissions = MYDB_READ | MYDB_WRITE

อย่างไรก็ตาม สิ่งนี้คล้ายกับวิธีจัดการสิทธิ์ของไฟล์ยูนิกซ์ หากคุณเคยสงสัยว่าทำไมคุณต้องใช้ตัวเลขมหัศจรรย์เพื่อให้ไฟล์เป็นแบบอ่านอย่างเดียว ตอนนี้คุณรู้แล้ว

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

แฮ็ก Bitwise ใน Ruby ใช้ AND ร่วมกับบิตมาสก์เพื่อตรวจสอบว่าบิตถูกตั้งค่าไว้หรือไม่

ใช้งานจริงน้อยลง (เว้นแต่คุณจะเป็นโปรแกรมเมอร์ C)

ตอนนี้ มาทำสิ่งมหัศจรรย์ทางคณิตศาสตร์กัน

ในอดีต การจัดการบิตถูกใช้เมื่อคุณพยายามบีบเศษเสี้ยวสุดท้ายของมิลลิวินาทีออกจากการคำนวณ อย่างที่คุณจินตนาการได้ มันถูกใช้อย่างมากโดยโปรแกรมเมอร์กราฟิกและคนอื่นๆ ที่ต้องการประสิทธิภาพเหนือสิ่งอื่นใด

ดังนั้นเทคนิคเช่นนี้จึงใช้ไม่ได้กับการพัฒนา Ruby ทุกวัน แต่ก็ยังเป็นแบบฝึกหัดการเรียนรู้ที่สนุกสนาน และอาจมีประโยชน์อย่างถูกกฎหมายหากคุณทำสิ่งต่างๆ เช่น การเขียนโปรแกรมระบบฝังตัว สำหรับการรักษาที่ละเอียดยิ่งขึ้น โปรดดูรายการเคล็ดลับการบิดเบี้ยวเล็กน้อย

การคูณและหารด้วยกำลังสอง

ลองดูการแสดงแทนเลขฐานสองของตัวเลข 1, 2, 4 และ 8 อย่างที่คุณเห็น การเพิ่มจำนวนเป็นสองเท่าเทียบเท่ากับการเลื่อนบิตทั้งหมดไปทางซ้ายเพียงตำแหน่งเดียว การลดจำนวนลงครึ่งหนึ่งก็เหมือนกับการขยับขวา

แฮ็ก Bitwise ใน Ruby การแทนค่าไบนารีของ 1, 2, 4 8

หากคุณยังจำได้ เรามีตัวดำเนินการ shift-left และ shift-right นั่นหมายความว่าเราสามารถคูณและหารด้วยกำลังสองได้ง่ายๆ โดยการขยับบิต

แฮ็ก Bitwise ใน Ruby คุณสามารถใช้ตัวดำเนินการกะระดับบิตเพื่อคูณหรือหารด้วยยกกำลังสอง

ค่าเฉลี่ยจำนวนเต็มบวกสองจำนวน

คุณสามารถบวกเลขจำนวนเต็มพื้นฐานสองจำนวนได้ดังนี้: (x+y) ==(x&y)+(x|y) ==(x^y)+2*(x&y) ในการคำนวณค่าเฉลี่ย สิ่งที่คุณต้องมีคือหารด้วยสองเล็กน้อย ซึ่งคุณสามารถหาได้จากตัวดำเนินการกะทางขวา

แฮ็ก Bitwise ใน Ruby คุณสามารถเฉลี่ยจำนวนเต็มบวกสองจำนวนดังนี้:(x&y)+((x^y)>>1)

รากที่สองผกผันอย่างรวดเร็ว

ฉันไม่สามารถโพสต์บล็อกบน bit twiddling โดยไม่รวมตัวอย่างที่เป็นตำนานที่สุดชิ้นหนึ่ง นั่นคือการประมาณรากที่สองแบบผกผันอย่างรวดเร็วของ John Carmack จากซอร์สโค้ดของเวที Quake 3 ปี 1999 อัลกอริธึมไม่ใช่ของเขา แต่การนำไปใช้ที่มีชื่อเสียงที่สุดคือ

ฉันจะไม่พยายามพอร์ตโดยตรงของสิ่งนี้ไปยัง Ruby เพราะมันทำงานโดยการสร้างการแสดงเลขฐานสองของตัวเลขทศนิยมในลักษณะที่ไม่สามารถแปลโดยตรงจาก 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, this can be removed

    return y;
}