โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

กลับลำดับบิต

กลับลำดับบิตต่ำสุดจำนวน width บิตของจำนวนที่กำหนด

สิ่งที่คุณจะได้เรียนรู้

  • อ่านบิตต่ำสุดด้วย AND 1
  • สร้างจำนวนทีละบิตด้วยการเลื่อนบิต
  • ทำงานภายในจำนวนบิตที่กำหนดตายตัว

โจทย์

ให้เขียน n เป็นเลขฐานสองให้มีจำนวน width บิตพอดี โดยเติมเลขศูนย์ข้างหน้าตามที่ต้องการ จากนั้นอ่านบิตเหล่านั้นย้อนกลับ เช่น n = 6 และ width = 4 จะได้ว่า 6 คือ 0110 เมื่อกลับลำดับก็ยังเป็น 0110 ผลลัพธ์จึงเป็น 6 แต่ถ้า width = 8 จะได้ 00000110 เมื่อกลับลำดับเป็น 01100000 ซึ่งเท่ากับ 96 การกลับลำดับบิตถูกนำไปใช้ในการแปลงฟูเรียร์แบบเร็ว (FFT) และเทคนิคการแฮชบางแบบ

จงเขียนฟังก์ชัน reverse_the_bits(n, width)

อินพุต

n: จำนวนเต็มที่ไม่เป็นลบซึ่งเขียนได้ภายใน width บิต

width: จำนวนบิตที่ต้องกลับลำดับ

เอาต์พุต

คืนค่าของรูปแบบบิตขนาด width บิตหลังกลับลำดับแล้ว

เงื่อนไข

1 ≤ width ≤ 63

0 ≤ n < 2^width

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 6
width = 8

ผลลัพธ์ที่คาดหวัง:
expected = 96
อินพุต:
long long n = 6;
long long width = 8;

ผลลัพธ์ที่คาดหวัง:
long long expected = 96;
อินพุต:
long n = 6;
long width = 8;

ผลลัพธ์ที่คาดหวัง:
long expected = 96;

คำอธิบาย

6 ในรูป 8 บิตคือ 00000110 เมื่อกลับลำดับได้ 01100000 ซึ่งเท่ากับ 96

ตัวอย่างที่ 2
อินพุต:
n = 1
width = 3

ผลลัพธ์ที่คาดหวัง:
expected = 4
อินพุต:
long long n = 1;
long long width = 3;

ผลลัพธ์ที่คาดหวัง:
long long expected = 4;
อินพุต:
long n = 1;
long width = 3;

ผลลัพธ์ที่คาดหวัง:
long expected = 4;

คำอธิบาย

1 คือ 001 เมื่อกลับลำดับได้ 100 ซึ่งเท่ากับ 4

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ทำซ้ำ width ครั้ง โดยดึงบิตต่ำสุดของ n ออกมา แล้วเลื่อน n ไปทางขวา

คำใบ้ 2

เลื่อนผลลัพธ์ไปทางซ้ายหนึ่งบิตก่อนบวกบิตที่เพิ่งดึงออกมา

คำใบ้ 3

เลขศูนย์นำหน้าของ n จะกลายเป็นเลขศูนย์ต่อท้ายของผลลัพธ์ ซึ่งการวนลูปจำนวนรอบคงที่จัดการให้เอง

ความซับซ้อนที่คาดหวัง

เวลา O(width), หน่วยความจำเพิ่ม O(1)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก