Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Đảo ngược các bit

Đảo ngược thứ tự của width bit thấp nhất của một số.

Bạn sẽ học được gì

  • Lấy bit thấp nhất bằng phép AND 1
  • Dựng một số từng bit bằng phép dịch
  • Tuân thủ độ rộng bit cố định

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.