เทคนิคการจัดการบิตทั่วไปมีอะไรบ้าง?

Question

IT Interview Practice · Accepted Answer

**การจัดการบิต** ดำเนินการโดยตรงบนการแสดงแทนด้วยเลขฐานสองของจำนวนเต็มโดยใช้ AND, OR, XOR, NOT และการเลื่อนบิต ช่วยให้การดำเนินการมีขนาดเล็ก ไม่มีสาขา และเร็วมาก ## การดำเนินการพื้นฐาน ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## เทคนิคที่มีประโยชน์ ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## ตัวอย่าง: หาตัวเลขเดียว (เทคนิค XOR) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## ความซับซ้อน การดำเนินการบิตคือ O(1); การสแกน XOR ด้านบนคือ **O(n) เวลา, O(1) พื้นที่**. ## เมื่อใดควรใช้ / ข้อสังเกต ใช้สำหรับ **bitmasks** (การแจงนับสับเซต, DP เหนือสถานะ), แฟล็ก, คณิตศาสตร์ที่เร็ว และโค้ดระดับต่ำ/ฝังตัว ระวังบิตเครื่องหมาย พฤติกรรมการเลื่อนเฉพาะภาษา และความสามารถในการอ่าน — แสดงความคิดเห็นเทคนิคที่ไม่ชัดเจน ## เหตุใดจึงสำคัญ การจัดการบิตให้ผลลัพธ์ที่หรูหรา O(1)-พื้นที่ (เช่นเทคนิค XOR สำหรับตัวเลขเดียว) ที่น่าทึ่งในการสัมภาษณ์ Bitmask DP ทำให้ปัญหา combinatorial state-space จำนวนมากสามารถแก้ไขได้ เป็นสิ่งจำเป็นในระบบ กราฟิก การบีบอัด และโค้ดที่สำคัญต่อประสิทธิภาพซึ่งทุกรอบมีความสำคัญ

การดำเนินการพื้นฐาน

เทคนิคที่มีประโยชน์

ตัวอย่าง: หาตัวเลขเดียว (เทคนิค XOR)

ความซับซ้อน

เมื่อใดควรใช้ / ข้อสังเกต

เหตุใดจึงสำคัญ

คำถามที่เกี่ยวข้อง