โจทย์
ให้เขียน 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
ตัวอย่าง
อินพุต:
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
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน