Đề bài
Viết n ở dạng nhị phân với đúng width bit, thêm số 0 ở đầu nếu cần, rồi đọc dãy bit đó theo chiều ngược lại. Với n = 6 và width = 4, 6 là 0110, đảo ngược vẫn là 0110, nên kết quả là 6. Với width = 8 thì có 00000110, đảo ngược thành 01100000, tức là 96. Phép đảo bit được dùng trong biến đổi Fourier nhanh (FFT) và trong một số kỹ thuật băm.
Hãy viết reverse_the_bits(n, width).
Đầu vào
n: Một số nguyên không âm, biểu diễn được bằng width bit.
width: Số bit cần đảo.
Đầu ra
Trả về giá trị của dãy width-bit sau khi đảo ngược.
Ràng buộc
1 ≤ width ≤ 63
0 ≤ n < 2^width
Ví dụ
Đầu vào:
n = 6
width = 8
Kết quả mong đợi:
expected = 96
Đầu vào:
long long n = 6;
long long width = 8;
Kết quả mong đợi:
long long expected = 96;
Đầu vào:
long n = 6;
long width = 8;
Kết quả mong đợi:
long expected = 96;
Giải thích
Với 8 bit, 6 là 00000110; đảo ngược thành 01100000, tức là 96.
Đầu vào:
n = 1
width = 3
Kết quả mong đợi:
expected = 4
Đầu vào:
long long n = 1;
long long width = 3;
Kết quả mong đợi:
long long expected = 4;
Đầu vào:
long n = 1;
long width = 3;
Kết quả mong đợi:
long expected = 4;
Giải thích
1 là 001; đảo ngược thành 100, tức là 4.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Lặp width lần: lấy bit thấp nhất của n, rồi dịch n sang phải.
Gợi ý 2
Dịch kết quả sang trái một bit trước khi thêm bit vừa lấy.
Gợi ý 3
Các số 0 ở đầu của n trở thành các số 0 ở cuối kết quả, và số lần lặp cố định đã lo việc đó.
Độ phức tạp mong đợi
thời gian O(width), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.