นับบิตและบิตที่ถูกตั้งค่าต่ำสุด
ใช้ popcount และเทคนิค n & -n
นับบิตและบิตที่ถูกตั้งค่าต่ำสุด เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
การนับบิตที่เป็น 1
หลายโจทย์ถามว่าตัวเลขหนึ่งมีบิตที่ถูกตั้งค่าไว้กี่บิต ซึ่งเรียกว่าจำนวนบิตที่เป็น 1 แนวคิดนี้ปรากฏในขนาดของสับเซต การตรวจสอบความเป็นคู่คี่ และการให้คะแนน 🔢
การนับในตัวของ Python
วิธีที่เร็วที่สุดในการนับบิตที่เป็น 1 คือเมธอดจำนวนเต็ม bit_count() ไม่ต้องใช้ลูป ไม่ยุ่งยาก ได้เพียงจำนวนบิตที่เป็น 1
print((13).bit_count()) # 0b1101 has 3 onesนับด้วย bin และ count
หากลืม bit_count ให้แปลงตัวเลขเป็นข้อความเลขฐานสองแล้วนับจำนวน 1 วิธีนี้ช้ากว่า แต่เข้าใจง่ายและจดจำได้สะดวก
print(bin(13).count('1')) # 3บิต 1 ตำแหน่งต่ำสุด
บิต 1 ตำแหน่งต่ำสุดคือเลข 1 ที่อยู่ขวาสุดในตัวเลข การแยกบิตนี้ออกมาเป็นเทคนิคสำคัญสำหรับต้นไม้ Fenwick และเทคนิคเกี่ยวกับสับเซตในภายหลัง
แยกออกด้วย n และ -n
เทคนิคที่มีชื่อเสียง n & -n จะเก็บไว้เฉพาะบิต 1 ตำแหน่งต่ำสุด การแทนค่าจำนวนลบแบบส่วนเติมเต็มสองทำให้เทคนิคนี้ทำงานได้อย่างน่าอัศจรรย์
n = 12 # 0b1100
print(n & -n) # 4 = 0b100เหตุใด n และ -n จึงใช้ได้
การทำให้เป็นลบจะกลับค่าทุกบิตแล้วบวก 1 ดังนั้นทุกตำแหน่งที่อยู่ต่ำกว่าบิต 1 ตำแหน่งต่ำสุดจะถูกกลับค่า การใช้ AND จึงเหลือเพียงบิตเดียวที่ยังคงอยู่
ล้างบิต 1 ตำแหน่งต่ำสุด
การลบ 1 จะยืมค่าผ่านเลขศูนย์ที่อยู่ต่อเนื่องกันด้านขวา ดังนั้น n & (n - 1) จึงลบบิต 1 ตำแหน่งต่ำสุดออก ทำซ้ำเพื่อเอาบิต 1 ออกทีละบิต
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000การนับแบบ Brian Kernighan
วนลูปขณะที่ตัวเลขไม่เป็นศูนย์ โดยล้างบิต 1 ตำแหน่งต่ำสุดออกในแต่ละครั้ง ลูปจะทำงานหนึ่งครั้งต่อบิต 1 จึงเหมาะสำหรับจำนวนบิตที่เป็น 1แบบเบาบาง
c = 0
while n:
n &= n - 1
c += 1ตรวจสอบว่าเป็นกำลังของสองหรือไม่
กำลังของสองที่เป็นบวกจะมีบิต 1 อยู่เพียงหนึ่งบิต ดังนั้น n & (n - 1) จึงเท่ากับ 0 ใช้ AND เพียงครั้งเดียวก็ตรวจสอบได้ทันที
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0ความเป็นคู่คี่จากจำนวนบิต
ความเป็นคู่คี่ของตัวเลขก็คือจำนวนบิตที่เป็น 1 หารด้วย 2 แล้วหาเศษ วิธีนี้ตอบคำถามว่ามีบิต 1 เป็นจำนวนคี่หรือคู่ได้ในขั้นตอนเดียว
parity = (13).bit_count() & 1 # 1เลือกเครื่องมือที่เร็วที่สุด
หากต้องการความเร็วสูงสุด ให้ใช้ bit_count หากต้องการไล่ดูบิต 1 ให้ใช้ลูป n & (n-1) การเลือกเครื่องมือที่เหมาะสมช่วยให้ผ่านข้อจำกัดด้านเวลาได้อย่างราบรื่น ⚡
ตรวจสอบอย่างรวดเร็ว
ทดสอบเทคนิคการแยกบิต 1 ตำแหน่งต่ำสุด
ทบทวน: การนับบิต
คุณสามารถนับบิต 1 ด้วย bit_count แยกบิต 1 ตำแหน่งต่ำสุดด้วย n & -n และลบบิตนั้นด้วย n & (n-1) ทั้งหมดนี้เป็นคำสั่งบรรทัดเดียวที่ทรงพลัง 🎉
คำถามที่พบบ่อย
บทเรียน “นับบิตและบิตที่ถูกตั้งค่าต่ำสุด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “นับบิตและบิตที่ถูกตั้งค่าต่ำสุด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “นับบิตและบิตที่ถูกตั้งค่าต่ำสุด”
ใช้ popcount และเทคนิค n & -n คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “นับบิตและบิตที่ถูกตั้งค่าต่ำสุด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- AND, OR, XOR และการเลื่อนบิต
- ตั้งค่า ล้าง และสลับบิต
- นับบิตและบิตที่ถูกตั้งค่าต่ำสุด
- บิตมาสก์ในฐานะเซตขนาดเล็ก