Bit Manipulation — พื้นฐาน & แนวคิด

Bit Manipulation (การจัดการบิต) คือการมอง integer (จำนวนเต็ม) เป็นชุดของ bits (บิต — เลข 0 กับ 1) แล้วเล่นกับมันตรง ๆ ด้วย bitwise operators (ตัวดำเนินการบิต) หลายโจทย์ที่ดูยากถ้าคิดเป็นเลขฐานสิบ จะกลายเป็นเรื่องง่ายและเร็วมากเมื่อคิดเป็น bits เพราะคอมพิวเตอร์ทำงานกับ bits ได้เร็วในระดับ hardware อยู่แล้ว หมวดนี้ใช้ตอนที่โจทย์เกี่ยวกับการนับ bits หาตัวที่ไม่ซ้ำ หรือจัดการค่าทีละ bit

เลขฐานสองเบื้องต้น

ทุก integer เก็บในคอมพิวเตอร์เป็นชุดของ bits เช่น เลข 13 ในฐานสิบ เขียนเป็นฐานสองได้ 1101 ซึ่งอ่านว่า 8 + 4 + 0 + 1 = 13 (bit ขวาสุดคือหลัก 1, ถัดมา 2, 4, 8 ไล่เป็นเท่าตัวไปเรื่อย ๆ)

ใน Python เราแปลงและดูค่าฐานสองได้ง่าย ๆ ด้วย bin() และเขียนเลขฐานสองตรง ๆ ด้วยคำนำหน้า 0b

print(bin(13))    # '0b1101'
print(0b1101)     # 13
print(13 >> 1)    # 6   เลื่อนบิตไปขวา 1 ตำแหน่ง (หารสองปัดลง)
print(13 << 1)    # 26  เลื่อนบิตไปซ้าย 1 ตำแหน่ง (คูณสอง)

ตัวดำเนินการบิต

bitwise operators จะทำงานกับ bits ทีละตำแหน่ง (bit position) พร้อมกันทุกตำแหน่ง มีดังนี้

เทคนิคบิตที่ต้องจำ

มีสองสามลูกเล่นที่โผล่มาในโจทย์บ่อยมาก จำไว้แล้วชีวิตง่ายขึ้นเยอะ

n = 12   # 0b1100

# 1) n & 1 เช็คว่าเลขคี่หรือคู่ (ดูบิตขวาสุด)
print(n & 1)         # 0  -> คู่  (ถ้าได้ 1 คือคี่)

# 2) n & (n - 1) ลบบิต 1 ที่อยู่ขวาสุดออกหนึ่งตัว
#    12 = 1100, 11 = 1011, 12 & 11 = 1000 (8)
print(n & (n - 1))   # 8

# 3) คุณสมบัติของ XOR
#    a ^ a = 0        เลขเดียวกัน xor กันได้ 0
#    a ^ 0 = a        xor กับ 0 ได้ตัวเดิม
#    xor สลับลำดับได้ (a ^ b ^ a = b)
print(7 ^ 7)         # 0
print(7 ^ 0)         # 7
print(7 ^ 3 ^ 7)     # 3