Mô phỏng thuật toán Đảo ngược các bit

Reverse Bits · Nhóm: Bit & Mặt nạ

Đảo ngược thứ tự các bit của một số rộng cố định: bit ở vị trí i đổi chỗ cho bit ở vị trí (width-1-i), đối xứng qua tâm.

Ý tưởng

Trải số thành dãy bit theo thứ tự MSB trước.

Dùng hai con trỏ đối xứng i = 0 và j = width-1, đổi chỗ hai bit rồi tiến vào tâm (i tăng, j giảm).

Khi hai con trỏ gặp nhau thì dừng, ghép lại dãy bit đã đảo thành số kết quả.

Vì sao đúng

Mỗi lần chỉ chạm hai vị trí đối xứng, tổng cộng width/2 lần đổi là lật xong toàn bộ; với số 8 bit chỉ cần 4 lần đổi, độ phức tạp O(width).

Mã Python

def reverse_bits(n, width=8):
    bits = [(n >> (width - 1 - k)) & 1  # MSB-first bit list
            for k in range(width)]
    i, j = 0, width - 1               # symmetric bit positions
    while i < j:                      # swap toward the center
        bits[i], bits[j] = bits[j], bits[i]
        i, j = i + 1, j - 1
    result = 0                        # rebuild the integer
    for b in bits:
        result = (result << 1) | b
    return result

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.